Count the pairs of positions i < j whose values add up to k.
What to build
A program that counts pairs of positions.
Requirements
- Read
n,kand the numbers. - Count the pairs with
i < jthat add up tok.
Input
The first line has n and k (n from 1 to 300). The second line has n whole numbers.
Output
The number of pairs.
Constraints
n is from 1 to 300.
Example
Input:
5 6
1 5 3 3 2
Output:
2
Why it works
The inner loop starts just after i, so each pair is looked at once. That is about n²/2 steps, which is fine at this size.
Examples
Example 1 · Input
5 6 1 5 3 3 2
Expected output
2
Example 2 · Input
3 10 1 2 3
Expected output
0
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Two loops (j starting at i + 1) check every pair once: O(n²).
Hint 2
Challenge: count it in O(n) with a dictionary of values seen so far.
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()]
count = 0
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == k:
count += 1
print(count)