Finding pair with sum between 1 and 2

Question

Given n positive real numbers, the task is to provide a YES or NO answer to the following question: "Does there exist a pair of numbers x and y such that 1 <= x+y <= 2.

The obvious solution is to sort all the numbers which will take O(nlogn). Now, pair can be checked in O(n) time.

However, the question is expected to be solved in constant space and linear time. Any insights?

Are the real numbers guaranteed to be nonnegative, or can you have both positive and negative numbers? — templatetypedef, Nov 04 '14 at 19:45
Hash all the numbers, and for every number check if 1-x or -x or 2-x exist. — WannaBeCoder, Nov 04 '14 at 19:50
This may seem odd, But since you said positive numbers, Count number of ones . If atleast two ones exist. then its possible. — WannaBeCoder, Nov 04 '14 at 19:54
I think this might be a duplicate because I remember reading the answer to this problem elsewhere on Stack Exchange. I'd prefer not to answer this question if I can find what it's a duplicate of, but I can't seem to find the original. — templatetypedef, Nov 04 '14 at 20:00
http://stackoverflow.com/questions/19557505/triplet-whose-sum-in-range-1-2 is this what you are talking about? @templatetypedef — WannaBeCoder, Nov 04 '14 at 20:01
@templatetypedef: I have tried searching for the question but I could not find it. PLease dont refrain from posting the answer if you know it due to this reason. :) — Bhoot, Nov 04 '14 at 20:02
@WannaBeCoder Ah, perhaps it was about triples of numbers. My mistake! — templatetypedef, Nov 04 '14 at 20:09
I guess the same solution can be extended to this case as well taking (0,1] as one range and (1,2) we cannot have two numbers from second range. We can have one number from first range and one from second. Two numbers from first range is also possible. Hope that helps. @Bhoot — WannaBeCoder, Nov 04 '14 at 20:16
Are there any restrictions on the maximum number of decimal places for a real number? — turingcomplete, Nov 04 '14 at 20:41
OP, can you give an example? Also, it might help to explain your 'obvious solution'. Your outline doesn't convince me it's correct. — Colonel Panic, Nov 06 '14 at 09:39

Pascal Cuoq · Accepted Answer · 2014-11-06T08:13:23.017

3

Only numbers between 0 and 2 are useful for participating in a winning pair. The others can be ignored.

Each such number x makes it possible to create a pair with one additional number from the list between 1-x and 2-x. Compute and maintain the acceptable bounds as you progress through the list. There cannot be more than two intervals of acceptable next values at any given time, because all the intervals of acceptable next values are included between -1 and 2 and have width 1. Therefore the acceptable next values to complete a pair can be represented in constant space.

Answer YES as soon as a number appears from the list that is in one of the at most two intervals of acceptable next values. Answer NO if you get to the end of the list without encountering the situation.

Example: 0.1, 0.5, 2.0 …

When starting, the set of values that can appear and complete a pair is the empty set.
After reading 0.1, the set of values that would complete a pair if they appeared now is [0.9, 1.9].
0.5 does not belong to the set of values that can complete a pair. However, after reading it, values in [0.5, 1.5] can complete a pair. Since we already had the set [0.9, 1.9], the new set of values that can complete a pair is [0.5, 1.9].
2.0 does not belong to the set of values that can complete a pair. However, we can now read any value in [-1, 0] to complete a pair. The new set of values that can be read to complete a pair henceforth is [-1, 0] ∪ [0.5, 1.9].
and so on…

edited Nov 06 '14 at 08:13

answered Nov 04 '14 at 20:03

Pascal Cuoq

79,187
7
161
281

I'm not sure I see why this works in linear time and constant space. Can you elaborate? – templatetypedef Nov 04 '14 at 20:09
@templatetypedef There is only one linear pass on the list of values. At each step, the algorithm tests if the new value is acceptable to complete a pair (constant time) and incorporates the new value in a representation of acceptable values from next step onwards, which also takes constant time. The most complex representation for the set of acceptable values to complete a pair is as two intervals, which occupies constant space. Note that the problem, as stated in the body of the question, only requires a “yes or no” answer. – Pascal Cuoq Nov 04 '14 at 20:14
@templatetypedef However, the winning pair can be produced in constant space and linear time, too. When the second value `y` of the pair has been found, the first value having been forgotten, it is enough to scan the list again looking for it (that is, looking for a number `x` such that `1 ≤ x + y ≤ 2`. – Pascal Cuoq Nov 04 '14 at 20:19
Got it. I misread your algorithm the first time around (I thought you were making multiple passes over the input, one for each element.) – templatetypedef Nov 04 '14 at 21:23
@PascalCuoq Could you please help me understand your algorithm - could you add an example with a small number of reals, showing how the time is kept linear? – גלעד ברקן Nov 05 '14 at 15:12
@גלעדברקן Example added. I do not see what is confusing in what I have already written in the two comments above, so I don't know what values would help see how it works. – Pascal Cuoq Nov 06 '14 at 09:24
@PascalCuoq Thank you! (Sometimes I need a more concrete example to help me understand.) – גלעד ברקן Nov 06 '14 at 15:40

score 3 · Answer 2 · answered Nov 04 '14 at 21:39

I like Pascal Cuoq's algorithm for this problem, which I think is a nice and elegant solution. I wanted to post a different approach here that gives a slightly different perspective on the solution.

First, here's the algorithm:

Make one pass over the input and keep track of the following: the smallest number between 1 and 2, the smallest number less than 1 the largest number less than 1/2, and the number of numbers between 1/2 and 1.
If the sum of the smallest number between 1 and 2 and the smallest number less than 1 is less than 2, output YES.
Otherwise, if there are at least two numbers between 1/2 and 1, output YES.
Otherwise, if there are no numbers between 1/2 and 1, output NO.
Otherwise, if the sum of the largest number less than 1/2 and the unique number in the array between 1/2 and 1 is greater than 1, output YES.
Otherwise, output NO.

Here's a proof of why this works. As Pascal noted, we only care about numbers in the range [0, 2); anything outside this range can't be part of something that sums up to between 1 and 2. We can do a case analysis to think about what the possible numbers in the sum could be.

First, it's possible that one of the numbers is in the range (1, 2). We can't have two numbers in this range, so the other number must be in the range [0, 1]. In that case, we can take the smallest number in the range [0, 1] and see what happens when we add it with the smallest number in the range (1, 2): if their sum is between 1 and 2, we're done; otherwise, no sum involving a number in the range (1, 2) can be part of the summation.

Otherwise, the summation must purely consist of numbers from the range [0, 1]. Notice that at least one of the numbers must be in the range [1/2, 1], since otherwise their sum can't be at least 1. Also note that the sum of any two numbers in this range will never exceed 2. In this case, if there are two numbers in the range [1/2, 1], their sum satisfies the condition and we're done. If there are 0 numbers in the range [1/2, 1], there is no solution. Otherwise, we can try adding the largest number in the range [0, 1/2) to the one number in the range [1/2, 1] and see if the sum is at least 1. If the answer is yes, we've got the pair; if not, the answer is no.

I definitely like Pascal's algorithm more than this one, but I thought I'd post this to show how a case analysis can be used here.

Hope this helps!

Thank you for the solid explanation. I can only upvote it though. Pascal's answer is more complete, so I have accepted that. — Bhoot, Nov 07 '14 at 08:14

Finding pair with sum between 1 and 2

2 Answers2