Not the exercise, just the fact it rests on. Pair the first number with the last, the second with the second-to-last, and every pair has the same total.
n = 10
print(sum(range(n + 1))) # -> 55 adding them up, one by one
print(n * (n + 1) // 2) # -> 55 the formula: no loop at all
# 0 + 10, 1 + 9, 2 + 8 ... every pair makes 10, and there are 11 numbers,
# so the total is 10 * 11 / 2.
print(len({3, 1, 3})) # -> 2 a set drops repeats, len() notices
- What the total should be
The numbers 0 to n always add up to n * (n + 1) // 2. Whatever is missing is the gap between that and what you actually have.
- // keeps it a whole number
n * (n + 1) is always even, so // divides exactly and the answer stays an int. / would give 55.0.
- A set is a cheap duplicate check
If len(set(numbers)) is smaller than len(numbers), something repeats. The arithmetic trick silently gives a wrong answer on repeats, so they have to be caught first.
You know which numbers there should be, so you know what they should add up to. What does that tell you about the one that is not there?
n is len(numbers). The full total is n * (n + 1) // 2. Take away sum(numbers), and what is left is the answer. Check the input first.
If the set of numbers is smaller than the list, or any number is below 0 or above n, raise ValueError. Then return the full total minus the sum.
def missing_number(numbers): n = len(numbers) if len(set(numbers)) != n or any(x < 0 or x > ____ for x in numbers): raise ValueError('not a set of tickets from 0 to n') return n * (n + 1) // 2 - ____(numbers)
def missing_number(numbers):
n = len(numbers)
if len(set(numbers)) != n or any(x < 0 or x > n for x in numbers):
raise ValueError("expected distinct numbers from 0 to n")
return n * (n + 1) // 2 - sum(numbers)
n numbers came back out of n + 1, so the range is 0..len(numbers). max(numbers) would be wrong when the missing one is n itself.
The formula assumes a valid input and gives a plausible wrong number when it is not. Two lines of checking turn a quiet wrong answer into a loud error.
The sum formula, and that the answer is linear time and constant extra memory apart from the check. Mentioning XOR as the version that never builds a large total is a bonus.
If more than one number can be missing, the sum only tells you what the missing numbers add up to, not what they are. Then a set of what you have, compared with range(n + 1), is the honest answer, and it is still one pass.
- Solve it with XOR instead of addition and explain why it works.
- Two numbers are missing: find both, still without sorting.
- The numbers run from 1 to n instead of 0 to n. What changes, and what stays the same?