Four List Zero Tuples
Problem
Four lists of equal length are given. Count the ways to pick exactly one value from each list so the four values add up to zero. Two picks count separately whenever they come from different positions, even if the values happen to be equal.
Examples
Input: a = [1, 2], b = [-2, -1], c = [-1, 2], d = [0, 2]
Output: 2
Why: 1 + (-2) + (-1) + 2 and 2 + (-1) + (-1) + 0 both reach zeroInput: a = [0], b = [0], c = [0], d = [0]
Output: 1
Why: there is only one pick to make and it worksInput: a = [1], b = [1], c = [1], d = [1]
Output: 0
Why: edge case, no combination can reach zeroHints
0 / 3
Trying all four positions at once costs the fourth power of the length. Notice that the four lists split naturally into two halves that can be handled separately.
Any winning pick is a pair from the first two lists plus a pair from the last two, and the two pair sums must be exact opposites of each other.
Tally every sum reachable from the first two lists into a map from sum to how many pairs produce it. Then form every pair from the last two lists and add the tally of the opposite sum to the running count.
Solution
Splitting the four lists into two halves turns a fourth-power search into two squared ones. Every pair from the first half is tallied by its sum, so a pair from the second half only has to look up the count of its exact opposite. Counting rather than storing the pairs themselves is what keeps the lookup constant time, and separate positions with equal values are naturally counted separately. Time is O(n squared) on average, and space is O(n squared) for the tally.
from collections import Counter
def count_zero_tuples(a, b, c, d):
# every sum reachable from the first half, with how many pairs make it
pair_sums = Counter(x + y for x in a for y in b)
total = 0
for x in c:
for y in d:
total += pair_sums.get(-(x + y), 0) # the exact opposite sum
return total
print(count_zero_tuples([1, 2], [-2, -1], [-1, 2], [0, 2])) # -> 2
print(count_zero_tuples([0], [0], [0], [0])) # -> 1
print(count_zero_tuples([1], [1], [1], [1])) # -> 0Stuck on the idea rather than the code? Two Sum covers it.