wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Array Problem (x-y=z for x,y in sorted array)
        
(Message started by: witee on Jul 13^th, 2010, 6:35am)

Title: Array Problem (x-y=z for x,y in sorted array)
Post by witee on Jul 13^th, 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 13^th, 2010, 6:50am

on 07/13/10 at 06:35:30, witee wrote:

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? ::)

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 13^th, 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 13^th, 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 15^th, 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 17^th, 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 18^th, 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:
(4₁,7₁), (4₁,7₂), (4₂,7₁), (4₂,7₂)
(looking for x+y=11 or x-y=-3)
That would make the output size O(n²) as worst case and no solution could be faster than that.

Title: Re: Array Problem
Post by birbal on Jul 24^th, 2010, 7:51am

on 07/18/10 at 14:11:23, Grimbal wrote:

Size of the output would be O(n²), 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 26^th, 2014, 10:28pm

Just want to see the solution