Overview
You do not need advanced mathematics for most DSA, but a handful of number-theory tools show up constantly: computing a greatest common divisor, listing primes, working "modulo 10⁹+7" so numbers don't overflow, and raising numbers to huge powers quickly. Aptitude-style coding rounds in campus placements lean heavily on exactly these.
The common thread is efficiency. Checking primality by trial division up to n is O(n); up to √n it is O(√n); the Sieve of Eratosthenes finds every prime up to n in O(n log log n). Recognising which tool fits turns a timeout into an instant answer.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| gcd(a, b) | O(log min(a, b)) |
| Primality by trial division | O(√n) |
| Sieve up to n | O(n log log n) time, O(n) space |
| Fast power aᵇ mod m | O(log b) |
Patterns to recognise
Reduce modulo at every step
Use it for: Answers "modulo 10⁹+7".
Apply % after every addition and multiplication, not only at the end, or intermediate values overflow.
Precompute with a sieve
Use it for: Many primality queries on numbers up to ~10⁷.
Build the sieve once, then answer each query in O(1).
Count factors, not products
Use it for: Trailing zeros, divisibility of factorials.
Trailing zeros of n! = number of factors of 5 in 1..n, because factors of 2 are always more plentiful.
Code template
MOD = 10**9 + 7
def gcd(a, b):
while b:
a, b = b, a % b
return a
def sieve(n): # all primes <= n
if n < 2:
return []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n ** 0.5) + 1):
if is_prime[p]:
for multiple in range(p * p, n + 1, p):
is_prime[multiple] = False
return [i for i, ok in enumerate(is_prime) if ok]
def mod_pow(base, exp, mod=MOD): # O(log exp)
result, base = 1, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
const long long MOD = 1'000'000'007LL;
long long gcdLL(long long a, long long b) {
while (b) { long long t = a % b; a = b; b = t; }
return a;
}
vector<int> sieve(int n) { // all primes <= n
vector<int> primes;
if (n < 2) return primes;
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (long long p = 2; p * p <= n; ++p)
if (isPrime[p])
for (long long m = p * p; m <= n; m += p) isPrime[m] = false;
for (int i = 2; i <= n; ++i) if (isPrime[i]) primes.push_back(i);
return primes;
}
long long modPow(long long base, long long exp, long long mod = MOD) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
Common mistakes
- Computing a × b before reducing when both are near 10⁹ overflows a 32-bit int — cast to 64-bit first.
- In Python, negative numbers with % return a non-negative result; in C++/Java they can be negative. Add mod before taking % again.
- Floating-point sqrt can be off by one for large n; prefer
p * p <= nloops.
Quick check
Three questions on Math. Get all three right to earn +15 XP.
-
What does gcd(48, 18) equal?
Euclid: gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = 6.
-
To test whether n is prime by trial division, up to which number must you try divisors?
If n = a x b, one of the two factors is at most sqrt(n), so checking up to sqrt(n) is enough.
-
Why do solutions compute (a * b) % MOD with 64-bit integers?
Two values near 1e9 multiply to about 1e18, which does not fit in 32 bits.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Fizz BuzzLeetCode Easy +20
- Palindrome NumberLeetCode Easy +20
- Greatest Common Divisor of StringsLeetCode Easy +20
- Count PrimesLeetCode Medium +40
- Factorial Trailing ZeroesLeetCode Medium +40
- Super PowLeetCode Medium +40
Stuck on Math?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor