Math & Number Theory for DSA: Complete Guide
Sanjeev SharmaAdvertisement
Why Math & Number Theory in DSA?
Mathematical algorithms power cryptography, combinatorics, and competitive programming. Understanding number theory unlocks O(log n) solutions to problems that naive approaches solve in O(n) or worse.
Core Topics
1. Prime Numbers
- Sieve of Eratosthenes O(n log log n)
- Segmented Sieve for large ranges
- Miller-Rabin probabilistic primality
2. GCD / LCM
- Euclidean algorithm O(log min(a,b))
- Extended Euclidean (Bezout coefficients)
- LCM = a * b / gcd(a, b)
3. Modular Arithmetic
- (a + b) % m, (a * b) % m
- Modular inverse: Fermat's little theorem
- Chinese Remainder Theorem
4. Fast Exponentiation
- Binary exponentiation O(log n)
- Matrix exponentiation for recurrences
5. Combinatorics
- nCr with precomputed factorials
- Pascal's triangle
- Catalan numbers
6. Number Theory
- Euler's totient function
- Prime factorization O(sqrt(n))
- Divisor sum / count
Complexity Summary
| Algorithm | Time | Space |
|---|---|---|
| Sieve | O(n log log n) | O(n) |
| GCD | O(log n) | O(1) |
| Fast Pow | O(log n) | O(1) |
| nCr precomputed | O(n) build, O(1) query | O(n) |
| Prime factorize | O(sqrt(n)) | O(log n) |
Interview Frequency
Math problems appear in 20-30% of coding rounds at Google, Meta, and competitive platforms.
Advertisement
