aloalgoMath & Number Theory Summary
A quick reference for math techniques and problems to practice. Mathematical concepts and number theory appear in coding interviews more often than you might expect. While you rarely need to prove theorems, knowing key formulas and algorithms like the Euclidean algorithm, the Sieve of Eratosthenes, and modular arithmetic can unlock elegant solutions that are impossible to achieve with brute force alone.Many math-based interview problems are disguised as array or counting problems. For example, finding a missing number in a sequence can be solved with the sum formula n*(n+1)/2, and computing the number of unique paths in a grid can be reduced to a combinatorics problem. The key is recognizing when a mathematical shortcut exists and applying it correctly.Key Concepts
The table below lists the most important mathematical algorithms and formulas for coding interviews. Each one solves a specific class of problems efficiently.| Concept | Formula/Algorithm | Time |
|---|---|---|
| GCD | Euclidean: gcd(a, b) = gcd(b, a % b) | O(log min(a,b)) |
| LCM | lcm(a, b) = (a * b) / gcd(a, b) | O(log min(a,b)) |
| Prime Check | Check divisors up to sqrt(n) | O(sqrt(n)) |
| Sieve of Eratosthenes | Mark multiples of primes | O(n log log n) |
| Modular Arithmetic | (a + b) % m = ((a % m) + (b % m)) % m | O(1) |
Common Formulas
These formulas come up frequently in interview problems. Memorizing them will help you recognize opportunities to replace O(n) loops with O(1) calculations and simplify complex counting problems.- Sum 1 to n: n * (n + 1) / 2. The classic formula attributed to Gauss. Use it to find missing numbers or compute expected sums.
- Sum of squares: n * (n + 1) * (2n + 1) / 6
- Geometric series: a * (1 - r^n) / (1 - r). Useful for problems involving exponential growth or decay.
- Combinations: C(n, k) = n! / (k! * (n-k)!). The number of ways to choose k items from n items regardless of order.
- Permutations: P(n, k) = n! / (n-k)!. The number of ways to arrange k items from n items where order matters.
Tips for Math Problems
- Watch for integer overflow: When multiplying large numbers, use modular arithmetic to keep values within bounds. Apply the modulo at each step rather than at the end.
- Use Python's built-in functions: Python provides math.gcd, math.lcm (Python 3.9+), and pow(a, b, mod) for modular exponentiation. These are well-tested and efficient.
- Look for patterns: Many math problems have patterns that emerge when you work through small examples by hand. Before coding, try the first few cases on paper.
Chapters
- GCD & LCM - Euclidean algorithm and applications
- Prime Numbers & Sieve - Primality testing and generation
- Modular Arithmetic - Operations under modulo
Practice Problems
- Missing Number - Use sum formula n*(n+1)/2 or XOR
- Unique Paths - Use combinatorics C(m+n-2, n-1) or DP
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.