Author |
Topic: Array Problem (x-y=z for x,y in sorted array) (Read 4091 times) |
|
witee
Newbie
Posts: 48
|
 |
Array Problem (x-y=z for x,y in sorted array)
« on: Jul 13th, 2010, 6:35am » |
 Quote  Modify
|
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? 
|
| « Last Edit: Jul 18th, 2010, 2:16pm by Grimbal » |
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender: 
Posts: 880
|
|
Re: Array Problem
« Reply #1 on: Jul 13th, 2010, 6:50am » |
Quote Modify
|
on Jul 13th, 2010, 6:35am, 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:
| hidden: | - 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 |
|
|
IP Logged |
|
|
|
nakli
Junior Member
Gender:
Posts: 62
|
|
Re: Array Problem
« Reply #2 on: Jul 13th, 2010, 8:10am » |
Quote Modify
|
This neatly finds one such pair(x,y).
How fast can we find all such existing pairs?
|
|
IP Logged |
I was born naked on a bed with a lady.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Array Problem
« Reply #3 on: Jul 13th, 2010, 2:56pm » |
Quote Modify
|
You can find the rest by continuing in the same way. Same time complexity.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Array Problem
« Reply #4 on: Jul 15th, 2010, 3:02pm » |
Quote Modify
|
Yep. Whenever you find a solution, print it and advance both i and j to the next higher value in the array.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Array Problem
« Reply #5 on: Jul 17th, 2010, 3:32am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Array Problem
« Reply #6 on: Jul 18th, 2010, 2:11pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Array Problem
« Reply #7 on: Jul 24th, 2010, 7:51am » |
Quote Modify
|
on Jul 18th, 2010, 2:11pm, Grimbal wrote: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. |
|
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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
qddaichy
Newbie
Posts: 1
|
|
Re: Array Problem (x-y=z for x,y in sorted array)
« Reply #8 on: Jan 26th, 2014, 10:28pm » |
Quote Modify
|
Just want to see the solution
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print