← All coding problems
Count Pairs With Given Sum
mediumPlacement Coding+20 XPTime limit 2s
Count the pairs of positions i < j with a[i] + a[j] = k. Pairs with equal values but different positions count separately: in [1, 1, 1] with k = 2 there are 3 pairs.
Input:
- line 1:
n k - line 2:
nintegers
Output: the number of pairs (it can be larger than 2³¹ — use 64-bit integers).
Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ values, k ≤ 10⁹.
Think about it: checking all pairs is O(n²). Walk left to right with a hash map of counts: when you reach x, every earlier k − x forms a pair with it. Then record x.
Sample input 1
4 6 1 5 7 1
Sample output 1
2
Sample input 2
3 2 1 1 1
Sample output 2
3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).