Math and Number Theory Patterns
The mathematics that turns up in interviews is a short list. Primes and factorisation, the Euclidean algorithm, modular arithmetic when answers must be reduced by a large prime, and enough combinatorics to count arrangements. What connects them is that each has one standard efficient method, and the gap between knowing it and not is usually the whole question.
Where to start, and what comes next
- 01
Primes & Factorisation
The sieve and trial division. Both are short, and the reasoning about why you can stop at the square root recurs throughout the topic.
- 02
GCD & Modular Arithmetic
The Euclidean algorithm and modular inverses. GCD appears constantly, and modular arithmetic is required whenever answers are taken modulo a large prime.
- 03
Combinatorics & Digits
Binomial coefficients under a modulus, and digit and base conversions. Both rely on the modular arithmetic above.
If you only have time for three things
- The sieve of Eratosthenes, including why marking starts at p squared rather than 2p.
- The Euclidean algorithm, and computing a least common multiple as a divided by the gcd, times b, dividing first to avoid overflow.
- Modular inverses via Fermat's little theorem, which requires the modulus to be prime, and knowing that the extended Euclidean algorithm covers the case where it is not.
Overflow is what this topic really tests. Java's int overflows silently at about two billion, so multiplying two large values before taking a modulus is wrong even though the final answer would fit. Say when you are switching to long and why. The other frequent check is stopping at the square root, and being able to explain why any composite must have a factor at or below it.
The idea underneath
Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.
Problems that use these patterns
Questions people ask
Why does the sieve start marking at p squared?
Every smaller multiple of p has a factor below p and was therefore already marked when that smaller prime was processed. Starting at 2p would be correct but would repeat work already done.
Why is a modular inverse needed at all?
Because modular arithmetic has no division. To divide by a under a modulus you multiply by the value that satisfies a times x equals 1, which is the modular inverse, and it only exists when a and the modulus are coprime.
When do I need to worry about overflow?
Any time you multiply two values that could each be near the int limit, and any time you sum a large series. The safe habit under a modulus of about 10 to the 9 is to hold intermediate products in a long, since two such values multiply to roughly 10 to the 18, which fits a long and does not fit an int.