Skills101
← 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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.