DSA & Algorithms
Part 7 of 16 · DSA Advanced & Company FavoritesMath & Number Theory for Interviews (gcd, mod, primes, combinatorics basics)
gcd/lcm, modular arithmetic, primes/sieve, and combinatorics basics asked in coding rounds.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The prompt is gcd, mod, primes, or combinations
Prefer
Use Euclid, binary exponentiation, or a sieve
Keep every multiplication inside the modulus.
- lcm is a*b/gcd.
- mod_pow is log time.
- nCr mod prime uses factorials or Lucas when asked.
Alternative
Loop and multiply in 64-bit integers
Intermediate products overflow and the sieve is rediscovered too late.
- You divide before you mod.
- You trial-divide up to n for every query.
- You call gcd a subtraction loop.
Reduce, then exponentiate
Stay inside the modulus.
- 1
Euclid for gcd
Replace a with b and b with a mod b. - 2
Binary exponentiation
Square the base, halve the exponent. - 3
Sieve once
Answer many prime queries from the table.
Overview
gcd/lcm, modular arithmetic, primes/sieve, and combinatorics basics asked in coding rounds.
When companies ask this
Recognition cues: gcd/lcm; mod pow; primes/Ugly Number; unique paths combinatorics; fraction / pow(x,n).
Mental model
Flow
- 1
1. Euclid gcd
- next2. lcm is a times b over gcd
- 2
2. lcm is a times b over gcd
- next3. Binary exponentiation
- 3
3. Binary exponentiation
- next4. Sieve primes once
- 4
4. Sieve primes once
Lesson map
Math & Number Theory for Interviews (gcd, mod, primes, combinatorics basics)
gcd/lcm, modular arithmetic, primes/sieve, and combinatorics basics asked in coding rounds.
Architecture. 1. Euclid gcd Ready. 2. lcm is a times b over gcd Ready. 3. Binary exponentiation Ready. 4. Sieve primes once Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Euclid["1. Euclid gcd Ready"] Lcm["2. lcm is a times b over gcd Ready"] Pow["3. Binary exponentiation Ready"] Sieve["4. Sieve primes once Ready"] Euclid -->|continues| Lcm Lcm -->|continues| Pow Pow -->|continues| Sieve
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Euclid O(log min(a,b)); sieve O(n log log n); mod_pow O(log exp).
- Pitfalls: overflow before mod; Fermat inverse only for prime mod; negative mod in some languages.
Interviewer traps
LeetCode drill (real problems)
- Pow(x, n)
- Sqrt(x)
- Count Primes
- Ugly Number
- Ugly Number II
- Excel Sheet Column Number
- Unique Paths
- Fraction to Recurring Decimal
- Super Pow
YouTube
Interview Q&A
Euclid?
Answer
gcd(a,b)=gcd(b,a%b).
lcm?
Answer
|a*b|/gcd careful overflow.
Binary exp?
Answer
Square base; multiply when odd bit.
Mod inverse?
Answer
An inverse exists only if gcd(a, m) = 1. Prime m with a not divisible by m: Fermat a^(m-2); otherwise extended Euclid.
Sieve start?
Answer
Mark from i*i.
Unique paths combo?
Answer
C(m+n-2, m-1) with care overflow.
Related?
Answer
binary-search (sqrt), bit-manipulation, dp.
Fraction recurring?
Answer
Map remainder -> index in decimal.