Practice: Pairing Race Times That Differ by Exactly Five Seconds

Six runners' times in seconds: count the pairs whose times differ by exactly 5, in one pass, including repeated times.

Counting the pairs that differ by a fixed amount in one pass takes a map of counts and two complements per item. Six runners finished a 400 metre race in 61, 66, 58, 71, 63 and 66 seconds. Count the pairs of runners whose times differ by exactly 5 seconds, in one pass over the times. Two runners share 66, and each of them pairs separately. Then decide what your code should return when the difference asked for is 0.

Show the count and a solution

Each time t pairs with an earlier time of t − 5 or t + 5, so it looks up both, adds how many earlier runners had each, and only then records t. A map of counts, rather than of indices, is what lets the second 66 pair with both the 61 and the 71. There are 5 pairs.

One pass over 61 66 58 71 63 66 for a difference of 5
Time	Looked up	Pairs added	Running total
61	56, 66	0	0
66	61, 71	1	1
58	53, 63	0	1
71	66, 76	1	2
63	58, 68	1	3
66	61, 71	2	5

With a difference of 0, t − 0 and t + 0 are the same key, and looking up both would count each earlier equal time twice, so the listing looks up once. Recording before looking up would pair every runner with themself.

race_times.pypy

def pairs_differing_by(times: list[int], difference: int) -> int:
    counts: dict[int, int] = {}
    pairs = 0
    for t in times:
        pairs += counts.get(t - difference, 0)
        if difference != 0:
            pairs += counts.get(t + difference, 0)
        counts[t] = counts.get(t, 0) + 1
    return pairs


times = [61, 66, 58, 71, 63, 66]
print("difference 5:", pairs_differing_by(times, 5))
print("difference 0:", pairs_differing_by(times, 0))
print("no runners:", pairs_differing_by([], 5))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

difference 5: 5
difference 0: 1
no runners: 0

Hash Tables

← → move through sections and cards