A sorted list has at most one pair of values that adds up to the target. Find it with two pointers, one at each end.
What to build
A search from both ends of a sorted list.
Requirements
- Read the list and the target.
- Print the pair, smaller first, or
NONE.
Input
The first line has n (2 to 20000). The second line has n different whole numbers in increasing order. The third line has the target.
Output
The two values, smaller first, separated by a space, or NONE.
Constraints
n is from 2 to 20000.
Example
Input:
6
1 3 4 6 9 11
13
Output:
4 9
Why it works
Moving the left pointer makes the sum bigger and moving the right pointer makes it smaller, so each step rules out a value.
Examples
Example 1 · Input
6 1 3 4 6 9 11 13
Expected output
4 9
Example 2 · Input
3 1 2 3 10
Expected output
NONE
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sum too small: move left up. Sum too big: move right down.
Solution
Show one correct solution (try it yourself first)
n = int(input())
nums = [int(x) for x in input().split()]
target = int(input())
left, right = 0, n - 1
answer = "NONE"
while left < right:
total = nums[left] + nums[right]
if total == target:
answer = f"{nums[left]} {nums[right]}"
break
if total < target:
left += 1
else:
right -= 1
print(answer)