|
||
Title: Array Problem (x-y=z for x,y in sorted array) Post by witee on Jul 13th, 2010, 6:35am Given a sorted array and a constant z, find two numbers x and y, if exist, s.t. x-y = z give the optimized solution? ::) |
||
Title: Re: Array Problem Post by pex on Jul 13th, 2010, 6:50am on 07/13/10 at 06:35:30, witee wrote:
There is a trivial O(n) algorithm: [hideb]- start with i=0, j=0 - at every iteration: - compute d = a[j]-a[i] - if d = z: done - if d > z: i++ - if d < z: j++ - terminate when an index runs out of bounds[/hideb] |
||
Title: Re: Array Problem Post by singh_sukhu on Jul 13th, 2010, 8:10am This neatly finds one such pair(x,y). How fast can we find all such existing pairs? |
||
Title: Re: Array Problem Post by towr on Jul 13th, 2010, 2:56pm You can find the rest by continuing in the same way. Same time complexity. |
||
Title: Re: Array Problem Post by Grimbal on Jul 15th, 2010, 3:02pm Yep. Whenever you find a solution, print it and advance both i and j to the next higher value in the array. |
||
Title: Re: Array Problem Post by pex on Jul 17th, 2010, 3:32am There are some issues with equal values though: suppose you are looking for a sum of 11 and the array is ... 4 4 ... 7 7 ... This means that there are four (4,7) pairs. After finding the first such pair, advancing one (or both) of the pointers will make you miss at least one other pair. So a bit of bookkeeping is required. |
||
Title: Re: Array Problem Post by Grimbal on Jul 18th, 2010, 2:11pm I understood the problem as following: find pairs (x,y) s.t. x and y exist in the array and x-y=z. So duplicates don't count. If duplicates did count, I would say in your case you need to return 4 pairs: (41,71), (41,72), (42,71), (42,72) (looking for x+y=11 or x-y=-3) That would make the output size O(n2) as worst case and no solution could be faster than that. |
||
Title: Re: Array Problem Post by birbal on Jul 24th, 2010, 7:51am on 07/18/10 at 14:11:23, Grimbal wrote:
Size of the output would be O(n2), we we need not iterate through each pair, we can count number of 4s ( 2 in this case) and number of 7s ( also 2 ) and can say ( 4 , 7 ) - 2*2 times. |
||
Title: Re: Array Problem (x-y=z for x,y in sorted array) Post by qddaichy on Jan 26th, 2014, 10:28pm Just want to see the solution |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |