Pigeonhole Principle

Introduction

The pigeonhole principle says that if more objects than boxes are distributed among the boxes, some box receives at least two objects. The statement is simple, but in algorithms the difficult part is choosing the right objects and boxes.

Repeated remainders, repeated states, nearby sorted values, and forced collisions are common forms of the principle.

Problem or motivation

Given $n$ integers, find a non-empty contiguous subarray whose sum is divisible by $n$.

Such a subarray always exists. We need to find one in $O(n)$.

Naive approach

We can test all $O(n^2)$ subarrays using prefix sums. This finds an answer but does not use the fact that an answer is guaranteed.