Math and number theory

First, how to attack these problems. They look frightening because they look like they need mathematics. But interview maths problems almost never use calculus or linear algebra. They ask something else: can you work through a few small cases by hand and notice a pattern, or an invariant — a quantity that stays the same through every step? Find it and the problem often collapses into one line. Miss it and you are stuck writing a brute-force simulation.

That is the pattern this chapter repeats. In the Nim game the invariant is the number of stones modulo 4. In the bulb problem it is whether the number of divisors is odd. For the majority element it is that the cancellation cannot finish. So the general routine is:

Now the rule the code cannot break: overflow and the modulus. Counting problems often have answers that are astronomically large (a number of combinations, a number of ways), so the statement asks for the result modulo 10⁹+7. That is not there to annoy you. It gives you a range where nothing overflows. But there is one rule: reduce as you compute, never only at the end. If you wait, the intermediate value has already overflowed into a wrong number, and a modulus applied afterwards cannot recover it. Reducing as you go is allowed because the modulus distributes over addition and multiplication:

The greatest common divisor (gcd) of two numbers is the largest number that divides both. The slowest method tries every value from min(a, b) downwards, which is O(min(a, b)). Euclid gave a much shorter route: gcd(a, b) = gcd(b, a % b). Repeat until the remainder is 0, and the divisor at that moment is the answer. This is the Euclidean algorithm.

Why is it valid? In one sentence: a and b have exactly the same common divisors as b and a % b. Suppose d divides both a and b. Because a % b = a − ⌊a/b⌋ × b, and every term on the right is a multiple of d, d also divides a % b. In the other direction, if d divides b and a % b, then a = ⌊a/b⌋ × b + (a % b) is a multiple of d as well. The two sets of common divisors are identical, so their largest members are equal — which is why replacing the pair with a smaller pair is safe.

How many steps? The remainder shrinks fast: after every two steps the larger value is at least halved. So the algorithm finishes in O(log min(a, b)) steps, and the gcd of two 64-bit numbers takes only a few dozen divisions.

The problem: count the primes below n. Brute force: for each x, try dividing by every value from 2 to √x. One number costs O(√x), so the total is about O(n√n), which is already slow at n = 10⁶.

Why is √x enough? If x = a × b and both factors were larger than √x, then a × b would be larger than x, which is impossible. So at least one of the two factors is at most √x. Any divisor above √x always comes with a partner below it, and testing up to √x finds that partner.

Turning it round: deciding whether a single x is prime is slow, but saying which numbers are composite is easy — a composite is a multiple of some prime. So stop testing numbers one by one. Instead, take each prime and cross out all of its multiples, and whatever is left is prime. This is the sieve of Eratosthenes. Watch it find the primes below 30:

The animation contains the two questions this problem is really about. First, why does the marking start at i²? When the sieve reaches the prime i, every multiple of i below i² has a prime factor smaller than i, and that smaller prime already crossed it out. Starting at i² skips all the repeated work. Second, why does the outer loop only need to reach √n? Every composite x ≤ n has a factor no larger than √x ≤ √n, so once all the primes up to √n have swept the board, everything still standing is prime.

Computing a^b by multiplying b times is O(b), which is hopeless at b = 10⁹. Fast exponentiation (also called binary exponentiation), covered in the divide and conquer chapter, brings it down to O(log b). The identity is a^b = (a²)^(b/2): square the base and halve the exponent. Equivalently, read the binary digits of b, and for every digit that is 1, multiply the matching a^(2ᵏ) into the result. b has only log b digits, so there are only log b squarings. Here we review the companion it always has in number theory: take the modulus after every multiplication.

Why discuss the modulus here? Because §01 left one gap: you cannot divide under a modulus, and fast power is the tool that closes it. Fermat's little theorem says that when m is prime and a is not a multiple of m, a^(m−1) ≡ 1 (mod m). Multiply both sides by the inverse of a and you get that the modular inverse of a is a^(m−2) mod m. So to compute (x ÷ a) % m, compute (x × a^(m−2)) % m instead — one call to fast power. Both conditions matter. If m is not prime, this formula is wrong, and you need the extended Euclidean algorithm from §02 instead.

The problem: one element appears more than n/2 times (the statement guarantees it exists); find it. Brute force: count with a hash map, O(n) time but O(n) space; or sort and take the middle element, O(n log n). Both are accepted. Neither is the best answer.

Can it be O(n) time and O(1) space? Yes, with one invariant. Keep a single candidate and a single count. For each value in turn: if it equals the candidate, add 1; if it differs, subtract 1; and when the count reaches 0, the next value becomes the candidate. This is Boyer-Moore voting. Step through it:

Why is the value left at the end always the majority? Read every −1 step as discarding a pair: one copy of the current candidate and one copy of a different value are thrown away together. So each −1 removes two values that are not equal. Now suppose one value appears more than n/2 times. All the other values together number fewer than n/2, so they run out before its copies do. It cannot be paired away completely, so it is the value that survives. That is the invariant that always holds.

The problem: rearrange the array into the next permutation in lexicographic order, that is, the smallest arrangement that is still larger than the current one. If it is already the largest, return the smallest. Brute force: generate all n! permutations, sort them, and look up the next one — already impossible at n = 10. The solution: think of it as adding one to a number and carrying. The pattern has four steps.

The intuition: if the suffix of a permutation is decreasing, that suffix is already its own largest arrangement, so nothing inside it can grow and the increase has to come from the position in front of it. So scan from the right for the first position that breaks the decreasing run, replace its value with the smallest value to its right that is still larger, and then make the right part as small as possible by putting it in increasing order. Frame by frame:

The problem: n stones on the table. You and your opponent take turns removing 1 to 3 stones, and the player who takes the last stone wins. Both play perfectly and you move first. Can you win? Brute force: a game search (minimax) over every possible move; the state space is O(n) and it times out. The solution: the routine from §01 — build a table, guess the pattern, prove it.

Play the small cases. n = 1, 2, or 3: take them all, so the first player wins. n = 4: whatever you take (1 to 3), you leave 1 to 3 stones for your opponent, who takes them all, so the first player loses. n = 5, 6, or 7: take 1, 2, or 3 to leave exactly 4 — the losing position — for your opponent, so the first player wins. n = 8: every move leaves 5, 6, or 7, all winning positions for your opponent, so the first player loses again. The pattern appears: the first player loses when n is a multiple of 4 and wins otherwise. The invariant is n % 4. Try it yourself — can you escape from a losing position?

Why does the invariant hold (proof by induction)? Call a position losing when the number of stones left is a multiple of 4 and it is your turn. (1) Base case: 0 stones and your turn means the previous player took the last stone and you have no move, so you lose — and 0 is a multiple of 4, which fits. (2) Induction: if you face a multiple of 4 and take k stones (1 to 3), your opponent takes 4−k and the pile is a multiple of 4 again, handed back to you. Repeating this leaves you 0. In the other direction, if n is not a multiple of 4, take n % 4 on the first move and your opponent faces a losing position. So the answer is one line:

The same "find the invariant" move clears a whole group of game and pattern problems. Two relatives from this chapter's problem set:

The problem: repeatedly replace a number by the sum of the squares of its digits. If it reaches 1, the number is called happy. For example 19: 1²+9² = 82, then 8²+2² = 68, then 6²+8² = 100, then 1²+0²+0² = 1. Happy.

The difficulty: a number that is not happy repeats forever and never reaches 1. Take 2:

The observation: treat "the next number" as a pointer — every number points at the sum of the squares of its digits. The whole process is then a linked list. For a happy number the chain ends at 1, which you can read as 1 pointing to itself. For an unhappy number the chain comes back to a value it has already visited, forming a cycle. So "does this chain reach 1" is the same question as "does this linked list contain a cycle" — which is the fast and slow pointer method (Floyd's cycle detection) from DataData · 03. Move the slow pointer one step and the fast pointer two steps: if they meet there is a cycle and the number is not happy; if the fast pointer reaches 1 first, the number is happy.

Why must it either reach 1 or repeat, instead of growing forever? Because the sum of squared digits cannot run away. The largest three-digit number is 999, and its sum of squares is 3 × 9² = 243, which is smaller than 999. The more digits a number has, the further the sum of squares falls behind it. So the value is quickly pushed into the finite range [1, 243]. A walk that keeps moving inside a finite set of states must, by the pigeonhole principle, either hit 1 or repeat a value — and a repeat is a cycle. There is always an outcome.