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.