Find every different pair of values that adds up to a target.
What to build
A program that uses a set of seen values and a set of pairs.
Requirements
- Read the numbers and
k. - Find every pair of values from two different positions that adds up to
k. - Print each different pair once, smaller value first, in increasing order.
- Print
NONEif there are no pairs.
Input
The first line has n and k. The second line has n whole numbers.
Output
One pair per line, separated by a space, or NONE.
Constraints
n is from 1 to 1000.
Example
Input:
6 7
1 6 2 5 3 4
Output:
1 6
2 5
3 4
Why it works
Checking against the values already seen means a value is only ever paired with an earlier one, so it cannot be paired with itself. A set of tuples removes repeated pairs automatically.
Examples
Example 1 · Input
6 7 1 6 2 5 3 4
Expected output
1 6 2 5 3 4
Example 2 · Input
5 4 2 2 2 1 3
Expected output
1 3 2 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each number x, look for k - x among the numbers you have already seen.
Hint 2
Store each pair as a tuple with the smaller value first, in a set.
Hint 3
sorted on a set of tuples orders them by their first value, then their second.
Solution
Show one correct solution (try it yourself first)
n, k = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
seen = set()
pairs = set()
for x in nums:
other = k - x
if other in seen:
pairs.add((min(x, other), max(x, other)))
seen.add(x)
if pairs:
for a, b in sorted(pairs):
print(a, b)
else:
print("NONE")