Write a function that takes a slice of integers and a target sum, then returns the number of distinct unordered value-pairs that sum to the target.
pairSum(nums, target)
A pair (a, b) and (b, a) count as the same pair. Two pairs with the same pair
of values count only once — so for [1, 1, 1] with target 2, the single value
pair (1, 1) counts as 1.
Input format: space-separated integers; the last value is the target.
pairSum([]int{1, 5, 7, -1}, 6) // → 2 (1+5=6, 7+(-1)=6)
pairSum([]int{1, 1, 1}, 2) // → 1 (only the value pair (1,1))
pairSum([]int{1, 2, 3}, 10) // → 0 (no pairs sum to 10)
The naive way to find pairs that sum to a target: compare every element against every other element — two nested loops, O(n²). It's also easy to get wrong here, because the problem doesn't want every matching index pair. It wants distinct unordered value pairs: (1, 1) counts once no matter how many 1's are in the list, and (a, b) is the same pair as (b, a).
For each number, ask: what value would need to have appeared earlier to pair with it? That's target - number, the complement. A set of values seen so far lets you check for the complement in near-constant time — the same trick that turns O(n²) into O(n) elsewhere. Checking against values seen so far (not the whole list) also means a lone number never pairs with itself: it can only match a partner that showed up earlier.
But this problem wants a count of distinct value pairs, not index pairs, and duplicate values shouldn't cause double-counting.
Take [1, 1, 1] with target 2. The second 1 finds a complement match with the first — a valid pair, count it. But the third 1 also finds a match, and if you count that too, you'd report 2 pairs when there's really only one distinct value pair: (1, 1).
The fix: track not just "which values have I seen" but also "which value-pairs have I already counted." Before incrementing your count, build a consistent identifier for the pair — the smaller value paired with the larger — and check whether you've already recorded it. Sorting the values into a consistent order matters, since (1, 5) and (5, 1) are the same pair and need the same identifier.
The seen-values set answers "can this number pair with something earlier?" in constant time, and the counted-pairs set answers "have I already credited this exact combination?" Together they give a correct count in one pass, trading O(n) extra memory for linear instead of quadratic time.
def pair_sum(nums, target):
seen = set()
counted = set()
count = 0
for num in nums:
complement = target - num
if complement in seen:
lo = min(complement, num)
hi = max(complement, num)
key = (lo, hi)
if key not in counted:
counted.add(key)
count += 1
seen.add(num)
return count
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.