Math for DSA: The Essential Topics for Coding Interviews
You do not need a math degree to be good at DSA. You need a small, focused toolkit: a handful of number-theory ideas (GCD, primes, modular arithmetic), comfort with logarithms and overflow, and fluency with bit manipulation (treating an integer as a row of on/off switches). This page maps out exactly what matters, why it shows up in interviews, and where to learn each piece in this section.
The math that actually appears in DSA
Most “math” problems in interviews reduce to a few recurring tools:
- Divisibility, GCD and LCM — reducing fractions, syncing cycles, grid problems. See GCD & LCM.
- Prime numbers and the sieve — factorization, counting primes, number theory. See Primes & Sieve.
- Modular arithmetic — answers “modulo 1e9+7”, hashing, fast exponentiation. See Modular Arithmetic.
- Bit manipulation — flags, sets, parity, and clever O(1) tricks. See Bit Manipulation Basics and Common Bit Tricks.
Integer overflow — the silent bug
A 32-bit signed integer maxes out near 2.1 billion (2^31 - 1); a 64-bit one near 9.2 × 10^18 (2^63 - 1). Multiplying two large ints can silently wrap around to a wrong (often negative) answer. The fix: use a wider type before the result can overflow.
// int * int overflows; cast one operand to a 64-bit type first
int a = 100000, b = 100000;
long long product = (long long)a * b; // 10,000,000,000 — correct// int * int overflows; cast one operand to long first
int a = 100000, b = 100000;
long product = (long) a * b; // 10000000000 — correct// Numbers are 64-bit floats: exact only up to 2^53 - 1.
// For bigger exact integers, use BigInt.
const a = 100000, b = 100000;
const product = BigInt(a) * BigInt(b); // 10000000000n — exact# Python ints are arbitrary precision — they never overflow.
a, b = 100000, 100000
product = a * b # 10000000000 — always correctLanguage note: This is the single biggest source of cross-language bugs. Python integers grow without limit. JavaScript numbers are 64-bit floats, exact only to
2^53 - 1(useBigIntbeyond that). C++ and Java have fixed-width integers that wrap silently — reach forlong/long long.
Logarithms in one minute
A logarithm answers “how many times can I halve n before reaching 1?” That count is log2(n). It’s why binary search and balanced trees are O(log n): each step throws away half the work. For n = 1,000,000, log2(n) is only about 20 — logarithmic algorithms barely notice large inputs.
Even/odd and divisibility checks
The cheapest math you’ll write. A number is even when its last bit is 0, which the modulo and bitwise-AND tests both capture:
bool isEven(int n) { return (n % 2) == 0; } // or: (n & 1) == 0boolean isEven(int n) { return (n % 2) == 0; } // or: (n & 1) == 0function isEven(n) { return (n % 2) === 0; } // or: (n & 1) === 0def is_even(n):
return n % 2 == 0 # or: (n & 1) == 0For beginners:
%is the remainder (“modulo”) operator.7 % 3is1because 7 divided by 3 leaves remainder 1. Watch out: in C++/Java/JS,-7 % 3is-1, while in Python it’s2— Python’s%follows the sign of the divisor. Modular arithmetic covers this.
How to use this section
- Read the five concept pages in order — each builds vocabulary used by the next.
- Pick your language once with the switcher; it persists across the whole course.
- Finish with the math & bit-manipulation exercises and check the solutions.
Going deeper: If you already know this material, jump straight to Common Bit Tricks and the exercises — the XOR and “power of two” problems are interview favorites.