35. Unique Pairs With Given Sum

Difficulty: easy · Array, Hashing, Two Pointers

Problem

Given an integer array `arr` and a target `sum`, count the **unique pairs** of values that add up to `sum`. A pair is two elements at different positions. Two pairs are the same if they consist of the same two values (order does not matter), so each distinct pair of values is counted once. A pair of equal values `(v, v)` counts only if `v` appears at least twice.

Input

- Line 1: the integer `n`. - Line 2: `n` space-separated integers. - Line 3: the integer `sum`.

Output

Print the number of unique pairs.

Example 1

Input:
4
1 2 3 4
5
Output:
2

Explanation: (1, 4) and (2, 3) both sum to 5, so the answer is 2.

Example 2

Input:
6
1 1 1 4 4 2
5
Output:
1

Explanation: Only the value pair (1, 4) sums to 5; it is counted once even though it can be formed many ways.

Example 3

Input:
3
3 1 5
6
Output:
1

Explanation: (1, 5) sums to 6; (3, 3) would need two 3s, but there is only one.

Constraints

- 1 <= n <= 10^5 - -10^9 <= arr[i] <= 10^9 - -2 * 10^9 <= sum <= 2 * 10^9

Solutions are judged against 3 sample and 9 hidden tests. Sign in to solve it · All problems