Math & Number Theory

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Interview number theory is five tools — gcd, the sieve, % M, fast power, nCr — plus digit peeling with % 10 and / 10.

   #1
2. { }template

   Euclid: while (b != 0) { int r = a % b; a = b; b = r; } return a; — O(log min(a, b)).

   #2
3. { }template

   Fast power: if ((e & 1) == 1) r = r * b % m; b = b * b % m; e >>= 1; — O(log e) steps.

   #3
4. ↯use it when

   "Modulo 10⁹+7" → reduce after every + and ×, long for products, divide by multiplying with a^(p−2).

   #4
5. O( )cost

   Sieve up to n: O(n log log n) time, O(n) memory. One number: trial division to √n, O(1) memory.

   #5
6. !trap

   (a * b) % M with ints overflows before the %. Write (long) a * b % M.

   #6
7. !trap

   Java's % keeps the left operand's sign: -7 % 3 == -1. Use Math.floorMod or ((x % m) + m) % m.

   #7
8. ✦pro tip

   Digit loops: guard rev > MAX / 10 before rev * 10 + d. Test 0, negatives and Integer.MIN_VALUE.

   #8
9. ↯use it when

   Weighted random → prefix sums + binary search for the first prefix[i] ≥ ticket.

   #9

Shaky on a card? Open the chapter or flip its recall cards.