Pairs that differ by k
Count the different pairs of values that are exactly k apart. About 9 minutes.
You know exactly who the partner is
A dating app pairs people whose ages differ by exactly k years. For someone aged x, the only partner that works is aged x + k. There's nothing to search for: just check whether anyone that age exists.
So count the values first, then walk through each different value once and ask whether value + k is there. Looking only upwards means each pair is found exactly once, from its smaller end.
- pairs
- 0
Count the values first: {3: 1, 1: 2, 4: 1, 5: 1}. Then walk each distinct value once.
When k is 0, you need a double
With k = 0, a value's partner is itself. That only makes a pair if the value appears at least twice. That's why you count the values rather than just putting them in a set: the counts tell you which values have a double.
Pairs are counted by value, so two 1s and one 3 still make just one pair (1, 3) when k is 2.
counts = {}
for x in nums:
counts[x] = counts.get(x, 0) + 1
if k == 0:
doubles = [c for c in counts.values()
if c > 1]
return len(doubles)
return sum(x + k in counts for x in counts)The numbers are 3, 1, 4, 1, 5 and k is 2. Which value pairs count?
- A(1, 3) and (3, 5)
- B(1, 3) twice, and (3, 5)
- COnly (3, 5)
Show the answer
(1, 3) and (3, 5). 1 + 2 = 3 and 3 + 2 = 5 are both there. The repeated 1 doesn't make a new pair.
Pairs that differ by k
You get a list of numbers and k ≥ 0. Count the different value pairs (a, b) with a ≤ b, both in the list (at different positions), and b − a = k.
nums = [3, 1, 4, 1, 5], k = 2 → 2
0 ≤ n ≤ 1,000,000 · 0 ≤ k ≤ 10^7