Math & Number Theory Master Recap: Interview Cheatsheet
Sanjeev SharmaAdvertisement
Math & Number Theory Master Recap
Algorithm Selection Guide
| Problem Pattern | Algorithm | Complexity |
|---|---|---|
| All primes up to n | Sieve of Eratosthenes | O(n log log n) |
| Factorize one number | Trial division | O(sqrt n) |
| Factorize many numbers | SPF sieve + lookup | O(n log log n) + O(log n) |
| GCD of two numbers | Euclidean | O(log min) |
| Modular inverse | Fermat (prime mod) | O(log mod) |
| Modular inverse | Extended GCD | O(log a) |
| a^n mod m | Binary exponentiation | O(log n) |
| nCr mod prime | Precomputed factorials | O(n) build, O(1) query |
| Fibonacci(10^18) | Matrix exponentiation | O(log n) |
| Count divisors | Factor then multiply exps | O(sqrt n) |
| Sum divisors | Factor then formula | O(sqrt n) |
| Euler totient(n) | Trial factorization | O(sqrt n) |
| All totients to n | Sieve | O(n log log n) |
| Convex hull | Graham scan | O(n log n) |
| Nim game | XOR all piles | O(n) |
| System of modular eq | CRT | O(k log m) |
| Range queries | Sqrt decomposition | O(sqrt n) |
Template Library
MOD = 10**9 + 7
# Fast power
def pw(b, e, m=MOD): return pow(b, e, m)
# Modular inverse (prime modulus only)
def inv(a, m=MOD): return pow(a, m-2, m)
# GCD/LCM
from math import gcd
def lcm(a, b): return a // gcd(a, b) * b
# Factorials for nCr
def build_fact(n, m=MOD):
f = [1]*(n+1)
for i in range(1,n+1): f[i]=f[i-1]*i%m
fi=[1]*(n+1); fi[n]=inv(f[n])
for i in range(n-1,-1,-1): fi[i]=fi[i+1]*(i+1)%m
return lambda n,k: f[n]*fi[k]%m*fi[n-k]%m if 0<=k<=n else 0
C = build_fact(10**6)
# Sieve
def sieve(n):
p=[True]*(n+1); p[0]=p[1]=False
for i in range(2,int(n**.5)+1):
if p[i]:
for j in range(i*i,n+1,i): p[j]=False
return p
# SPF sieve
def spf_sieve(n):
s=list(range(n+1))
for i in range(2,int(n**.5)+1):
if s[i]==i:
for j in range(i*i,n+1,i):
if s[j]==j: s[j]=i
return s
Top 25 Math/Number Theory LeetCode Problems
| # | Problem | Key Technique |
|---|---|---|
| 50 | Pow(x,n) | Binary exponentiation |
| 69 | Sqrt(x) | Binary search |
| 149 | Max Points on a Line | GCD slope normalization |
| 172 | Factorial Trailing Zeros | Count factors of 5 |
| 204 | Count Primes | Sieve |
| 231 | Power of Two | n & (n-1) == 0 |
| 263 | Ugly Number | Divide by 2,3,5 |
| 292 | Nim Game | n%4 != 0 |
| 338 | Counting Bits | dp[i] = dp[i>>1]+(i&1) |
| 342 | Power of Four | n&(n-1)==0 and n%3==1 |
| 365 | Water and Jug | GCD Bezout |
| 372 | Super Pow | Modular exp |
| 412 | Fizz Buzz | Modulo |
| 441 | Arranging Coins | Quadratic formula |
| 462 | Min Moves II | Median |
| 492 | Construct Rectangle | Sqrt then iterate down |
| 509 | Fibonacci | DP or matrix |
| 523 | Continuous Subarray Sum | Prefix mod hashmap |
| 593 | Valid Square | Dist sort + check |
| 628 | Max Product 3 | Sort + consider negatives |
| 812 | Largest Triangle Area | Convex hull or brute force |
| 878 | Nth Magical Number | Binary search + LCM I-E |
| 1201 | Ugly Number III | I-E with LCM |
| 1492 | kth Factor of n | Iterate sqrt |
| 1979 | Find GCD of Array | Min, max, gcd |
Common Pitfalls
- Overflow: Use
long longin C++; Python handles it natively - Float comparison: Use
abs(a-b) < 1e-9, nota == b - Fermat's inverse: Only works when modulus is prime
- GCD of 0:
gcd(0, n) = n— handle in LCM to avoid div by zero - Sieve optimization: Start inner loop at
p*p, not2*p - nCr for large n: Always precompute factorials, don't compute inline
Interview Mindset
- Math problems often have O(1) formulas — look for the pattern first
- Binary search on the answer works when the answer has monotone feasibility
- GCD/LCM often unlocks number theory problems involving multiples
- XOR is your friend for parity, single-occurrence, and Nim-style games
- When stuck, try small examples and look for patterns in the sequence
Advertisement
