Search for a pair with a sum of 1 to 2

Question

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

The obvious solution is to sort all the numbers that O (nlogn) will take. Now the pair can be checked at O ​​(n) time.

However, the issue is expected to be resolved in constant space and linear time. Any ideas?

Answer 1

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

Each such number x allows you to create a pair with one additional number from the list between 1-x and 2-x . Calculate and maintain acceptable boundaries as you move through the list. At any given time, there can be no more than two intervals of admissible next values, since all intervals of admissible next values ​​are included between -1 and 2 and have a width of 1. Therefore, the permissible next values ​​for completing a pair can be represented in constant space.

Answer YES as soon as a number from the list appears that is in one of no more than two intervals of valid following values. Answer NO if you reach the end of the list without encountering a situation.

Example: 0.1, 0.5, 2.0 ...

• At startup, the set of values ​​that may appear and complete the pair is empty.

• After reading 0.1, the set of values ​​that would complete the pair if they appeared is now [0.9, 1.9].

• 0.5 does not belong to a set of values ​​that can complete a pair. However, after reading the values ​​in [0.5, 1.5] may end. Since we already had a lot of [0.9, 1.9], the new set of values ​​that can complete the pair is [0.5, 1.9].

• 2.0 does not belong to a set of values ​​that can complete a pair. However, now we can read any value in [-1, 0] to complete the pair. A new set of values ​​that can be read to complete the pair later, [-1, 0] ∪ [0.5, 1.9].

• and so on...

Answer 2

I like Pascal Quoc's algorithm for this problem, which I consider to be a good and elegant solution. I would like to publish here a different approach, which gives a slightly different perspective in the solution.

Firstly, here is the algorithm:

• Take one pass over the entrance and track 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 from 1/2 to 1.
• If the sum of the smallest number between 1 and 2 and the smallest number less than 1 is less than 2, print YES.
• Otherwise, if there are at least two numbers between 1/2 and 1, print YES.
• Otherwise, if there are no numbers between 1/2 and 1, output NO.
• Otherwise, if the sum of the largest number is less than 1/2 and the unique number in the array between 1/2 and 1 is greater than 1, print YES.
• Otherwise, print NO.

Here is a proof of why this works. As Pascal noted, we are only interested in numbers in the range [0, 2]; anything outside this range cannot be part of something that sums between 1 and 2. We can do a case analysis to think about what possible numbers can be in the sum.

Firstly, it is possible that one of the numbers is in the range (1, 2). We cannot have two numbers in this range, so another number must be in the range [0, 1]. In this 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, done; otherwise, the sum of the sums including the number in the range (1, 2) may be part of the summation.

Otherwise, the summation should consist only of numbers from the range [0, 1]. Please note that at least one of the numbers must be in the range [1/2, 1], since otherwise their sum cannot 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 are done. If there are 0 numbers in the range [1/2, 1], there is no solution. Otherwise, we can try to add the largest number in the range [0, 1/2) to one number in the range [1/2, 1] and see if the sum is at least 1. If the answer is yes, we have a pair; if not, the answer will be no.

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

Hope this helps!