More items than boxes
Among any 13 people, at least two have their birthday in the same month. Nobody has to be asked: there are 12 months, and 13 people cannot all have different ones. The pigeonhole principle is this argument in general, with items in place of people and boxes in place of months.
The argument says that two people share a month. It does not say which month or which two people. Some problems only need to know that a repeat exists. When a problem asks for the repeat itself, we still have to search for it, and the principle can tell us how long the search takes or where to look.
Definition
If or more items are placed in boxes, at least one box holds two or more items.
The principle needs strictly more items than boxes. Twelve people can have twelve different birth months, and only the thirteenth forces a shared one.
The count scales up as well. With more than items in boxes, some box holds more than . Among 25 people, some month has at least three birthdays, because two per month accounts for only 24 people.
Remainders as boxes
In problems about numbers, the boxes can be remainders. Dividing a number that is not negative by leaves a remainder from 0 to , so there are exactly boxes, and any integers put two in the same one. Here are four numbers placed by their remainder when divided by 3:
The two numbers that landed together, 9 and 18, differ by a multiple of 3. That is true of any two numbers in one box. If and have the same remainder , the remainders cancel in the difference:
So among any integers, two differ by a multiple of . Any four integers contain two whose difference is divisible by 3. Any 11 integers contain two whose difference is divisible by 10, which for positive integers means two that end in the same digit.
Python's % returns a value from 0 to for a negative number as well, so negative integers go into the same boxes.
Drop numbers into remainder boxes
Drop the numbers into the box of their remainder one at a time, until one lands in a box that is already occupied. With 4 numbers, mod 3, the fourth number has nowhere new to go. With 11 numbers, mod 10, the first ten fill all ten boxes, and the eleventh has to repeat a last digit.
Deeper read: a run of neighbours whose sum is divisible by n
Any list of integers contains a run of one or more neighbouring numbers whose sum is divisible by . Take 3, 1, 4, 1, where . The running totals, with a 0 before the first number, are 0, 3, 4, 8, 9. That is totals but only 4 possible remainders of a division by 4, so two of the totals share a remainder. Here the remainders are 0, 3, 0, 0, 1, and the totals 0 and 4 both leave 0.
Two totals in the same remainder box differ by a multiple of , and their difference is the sum of the numbers between them: . The argument uses nothing about the particular numbers, so it holds for every list. It is also an algorithm: record the position where each remainder first occurs, stop at the first repeat, and the numbers between the two positions are the run. These running totals are called prefix sums, and the widget's example Prefix sums of 3, 1, 4, 1, mod 4 places them in their boxes.
Repeats in a process with few possible values
The items do not have to exist all at once. They can be the values a variable takes on successive turns of a loop, and then the principle limits how long the loop can run before a value comes back.
Long division shows it. To write as a decimal, we start with the numerator 1 as the first remainder. Each step multiplies the remainder by 10 and divides by 7. The quotient is the next digit, and the remainder is carried into the next step:
| Remainder | Times 10 | Divided by 7 | Digit | New remainder |
|---|---|---|---|---|
| 1 | 10 | 1 | 3 | |
| 3 | 30 | 4 | 2 | |
| 2 | 20 | 2 | 6 | |
| 6 | 60 | 8 | 4 | |
| 4 | 40 | 5 | 5 | |
| 5 | 50 | 7 | 1 |
After six steps the remainder is 1 again, the value the division started with. A step depends on nothing but the current remainder, so the seventh step repeats the first, the eighth repeats the second, and the same six digits come round forever:
The pigeonhole principle predicts a repeat without any of this arithmetic. A remainder of a division by 7 is one of the seven values 0 to 6, so among the first eight remainders two must be equal. For any denominator , a remainder comes back within steps. The program below marks each remainder in a list as it occurs and stops at the first one it has seen before:
def digits_until_repeat(d):
seen = [False] * d
r = 1 % d
digits = ''
while not seen[r]:
seen[r] = True
r *= 10
digits += str(r // d)
r %= d
return digits
print(digits_until_repeat(7))
print(digits_until_repeat(6))
print(len(digits_until_repeat(97)))The while loop has no counter, yet it cannot run more than times: every turn marks a remainder that was not marked before, and there are only of them. For 97 it runs 96 times: every remainder except 0 occurs before one comes back. Most denominators repeat much sooner. For 11 the loop stops after two digits, since , and for 6 it also stops after two digits, because has the remainders 1, 4, 4: the value that comes back is 4, and the starting remainder 1 never does. The first remainder is 1 % d and not 1 so that starts at remainder 0, the only entry its list has.
Find the repeated value by counting
The principle can also guide the search for a repeat that it shows must exist.
You get an array nums of integers, each between 1 and . One value appears two or more times, and every other value at most once. Return the repeated value without changing the array and using only constant extra memory.
Constraints
nums.length-
nums[i] - Exactly one value appears more than once
Sample 1 · Input
nums = [1,3,4,2,2]
Output
2
Sample 2 · Input
nums = [3,1,3,4,2]
Output
3
Sample 3 · Input
nums = [3,3,3,3,3]
Output
3
Here the numbers are the items and the values 1 to are the boxes. There are numbers and values, so some value repeats, as the statement says. The work is to find it without changing the array and with only constant extra memory. Sorting would put the equal numbers side by side, but it changes the array. A seen list like the one in the last part finds the repeat in one pass, but it takes flags of extra memory. Counting how often each value from 1 to occurs needs only a counter, but it makes up to passes over numbers, about comparisons for , or 100 seconds.
Counting a whole range of values at once does much better, and the pigeonhole principle says how to read the count. We pick a value and count the numbers in the array that are at most . Each of those numbers is one of the values 1 to . If the count is more than , there are more numbers than values for them, so some value from 1 to repeats.
If the count is or less, we look at the other numbers instead: at least of them are above , and only values are above , so some value above repeats. The array has only one repeated value, so in both cases the value that repeats is the answer, and one pass over the array has told us which side of it is on.
Now we choose in the middle of the values that are still possible. Each pass rules out half of them, and the search ends when one value is left. For [1, 3, 4, 2, 2], where :
| Values still possible | Test | Numbers at most | Conclusion |
|---|---|---|---|
| 1 to 4 | 2 | 3 (they are 1, 2, 2) | : the repeat is in 1 to 2 |
| 1 to 2 | 1 | 1 (it is 1) | : the repeat is above 1 |
| 2 to 2 | one value left: the answer is 2 |
def find_duplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
v = (low + high) // 2
at_most_v = sum(1 for x in nums if x <= v)
if at_most_v > v:
high = v
else:
low = v + 1
return low
print(find_duplicate([1, 3, 4, 2, 2]))
print(find_duplicate([3, 1, 3, 4, 2]))
print(find_duplicate([3, 3, 3, 3, 3]))The values still possible run from low to high, which start at 1 and . When more than v numbers are at most v, the repeat is at most v, so high moves down to v. Otherwise it is above v, and low moves up to v + 1. Each pass counts every entry of the array that is at most v, not only the entries from low up: the pigeonhole test compares those entries with the v values 1 to v, and low only records which values earlier passes ruled out. The function keeps three variables and a counter, and never writes to the array.
This is binary search, run over the range of values instead of the positions of a sorted array: each pass answers one yes-or-no question and halves the values still possible.
Cost of finding the repeat
- Count each value separately
time, memory - Up to passes over numbers: about comparisons for .
- Mark values in a `seen` list
time, memory - One pass, but extra flags, which the problem does not allow.
- Halve the range of values
time, memory - Halving values down to one takes 17 passes, since is the first power of two above . At 100,001 numbers a pass, that is about comparisons.
There is also a method that takes time with constant memory. It reads each number as the position to visit next and finds the loop that the repeated value creates. The Linked lists lesson teaches it as Floyd's cycle detection.
Common pigeonhole mistakes
Expecting a repeat from items in boxes.
- Where it breaks
- Ten integers can end in the ten different digits 0 to 9. Only an eleventh forces two of them to share a last digit.
- The fix
- Count at least items for boxes.
Testing
at_most_v >= vin the search for the repeat.- Where it breaks
- For
[1, 3, 4, 2, 2]the test passes at , where three numbers are at most 2, and then passes wrongly at , where one number is at most 1. The search returns 1, but the answer is 2. - The fix
- A range of values holds a repeat only when it holds more than numbers: test
at_most_v > v.
Waiting for the starting value to come back.
- Where it breaks
- The remainders of are 1, 4, 4, 4 and so on. A loop that stops when the remainder is 1 again never stops.
- The fix
- Mark every value that occurs and stop when any of them occurs a second time.
Recall A loop starts with x = 2 and keeps replacing x with (x × x + 1) % 1000. Without running it, what is the most turns it can take before x has a value it has had before?
After a turn, is a remainder of a division by 1000, one of the 1000 values 0 to 999, and the starting value 2 is one of them too. The start and the values after the first 1000 turns are 1001 values, so two of them are equal, and a value comes back within 1000 turns. From then on the loop repeats itself, because each new value depends only on the one before it.