Free Hashing lessonsHashing · Stage 2 · Counting with maps · Step 3

Meet in the middle

Count ways to pick one number from each of four lists that sum to zero. About 10 minutes.

Split four numbers into two pairs

You pick one number from each of four lists, and you want them to add up to 0. Trying every combination is n × n × n × n: for lists of 200 that's 1.6 billion.

But "a + b + c + d = 0" is the same as "a + b = −(c + d)". So work out every a + b and count how often each sum happens. Then for every c + d, look up its negative: that count is how many ways it completes a zero.

First half: count every a + b.

Second half: each c + d looks up its negative.

a = [1, 2], b = [-2, -1], c = [-1, 2], d = [0, 2]

b = -2b = -1

a = 1

-1

a = 2

a+b map: {-1: 1}

Step 1: every a + b. 1 + (-2) = -1.

Move 1 of 5

Two-sum, one level up

This is the two-sum trick again, with bigger pieces. There, each number looked for the one partner that completed the target. Here, each pair's sum looks for the pairs that cancel it out.

Use counts, not just "is it there?": several different a + b pairs can share the same sum, and each makes a different combination.

Count, don't just check: several pairs can share a sum.

In code

sums = {}
for x in a:
    for y in b:
        sums[x + y] = sums.get(x + y, 0) + 1
total = 0
for x in c:
    for y in d:
        total += sums.get(-(x + y), 0)
return total

Quick check

The first half says a + b = 3 happened 4 times. A pair from the second half has c + d = −3. How many combinations does it complete?

Show the answer

4. It completes each of the 4 first-half pairs that sum to 3.

Your problem

Four lists, sum zero

You get four lists a, b, c and d of the same length n. Count the ways to choose positions i, j, k, l with a[i] + b[j] + c[k] + d[l] = 0.

Example

a = [1, 2], b = [-2, -1], c = [-1, 2], d = [0, 2] → 2

1 ≤ n ≤ 200 · −2^28 ≤ each value ≤ 2^28 · return a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.