DSA Notes

Math

Pigeonhole & Modulo

More items than boxes means some box holds two.

The idea

The pigeonhole principle (Dirichlet’s principle): put n + 1 items into n boxes and at least one box contains two or more. It proves that something must exist without finding it by search.

A classic use: among the m + 1 prefix sums P[0], …, P[m] taken modulo m there are only m possible remainders, so two are equal, and the elements between them sum to a multiple of m.

So an array longer than m always contains such a block, and remembering where each remainder first appeared finds one in a single pass.

Sample problem

523. Continuous Subarray Sum ↗ Medium

Decide whether an array has a contiguous subarray of length at least 2 whose sum is a multiple of k.

nums = [1,2,6,4,3], k = 7
output = true   ([4,3])

Why the solution works

The sum of nums[l..r] is the difference of two prefix sums. It is a multiple of k exactly when those two prefix sums leave the same remainder modulo k.

So scan once, keeping the remainder of the running prefix sum and a map from each remainder to the earliest index where it occurred. Seeing a remainder again, at least two positions later, proves a valid block exists.

This is the pigeonhole principle at work: there are only k possible remainders, so once there are more than k prefixes, two of them must collide.

Complexity: O(n) time, O(min(n, k)) memory.

Watch out

  • In C++ the remainder of a negative number is negative: use ((x % m) + m) % m.
  • Count the empty prefix P[0] among the pigeons.
  • The principle proves existence. To output the block, remember where each remainder first appeared.
Watch it run

Try your own input

Practise on LeetCode