Query Before Insert

core

Implement pair_count(a, target) returning the number of index pairs (i, j) with i < j and a[i] + a[j] == target. Index pairs, not value pairs: if three elements all equal 3 and target is 6, that is three pairs. Values may repeat and may be negative, and the count can exceed a 32-bit integer, so return a 64-bit result.

Do it in one pass with a map from value to how many times that value has been seen. For each element x, first look up target - x in the map and add its count to the answer, then record x. That order is the mechanic: the map must only ever hold elements strictly to the left of the current one, so every pair is counted once, at its right-hand element. Recording x before the lookup lets an element pair with itself whenever 2 * x == target, which is silent on inputs where no value is exactly half the target, exactly the inputs people hand-trace.

Example: pair_count({3, 3, 3}, 6) returns 3: the pairs (0,1), (0,2) and (1,2). Scanning left to right, the first 3 sees an empty map and adds nothing, the second sees one earlier 3, and the third sees two, for 0 + 1 + 2 = 3.

Input format: each test in tests/*.in is laid out as:

Line 1: n, the array length.
Line 2: the n values, space-separated.
Line 3: target, the pair-sum to count.

Test 06.in reads:

1
7
14

This is a single element 7 with target = 14: tempting, but one element cannot pair with itself, so the count is 0.

Where you'll use it:

✦ Solution & editorial unlock with the pass.