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?

Answer 1

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…

Answer 2

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:

1. 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.
2. If the sum of the smallest number between 1 and 2 and the smallest number less than 1 is less than 2, output YES.
3. Otherwise, if there are at least two numbers between 1/2 and 1, output YES.
4. Otherwise, if there are no numbers between 1/2 and 1, output NO.
5. 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.
6. 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!