➗ Math
One-line summary: Number theory, combinatorics, and arithmetic tricks — the foundation of competitive programming warm-ups.
Diagram
Key Topics
| Topic | Key Insight |
|---|---|
| GCD / LCM | Euclidean: gcd(a,b) = gcd(b, a%b) |
| Sieve of Eratosthenes | Find all primes ≤ n in O(n log log n) |
| Modular Arithmetic | (a+b)%m = ((a%m)+(b%m))%m |
| Combinatorics | nCr = n! / (r! * (n-r)!) |
| Trailing zeros in n! | Count factor-5s: ⌊n/5⌋ + ⌊n/25⌋ + ... |
| Perfect square | Math.sqrt(n) % 1 === 0 |
Common Patterns
GCD / LCM
function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
function lcm(a, b) { return (a / gcd(a, b)) * b; }
Sieve of Eratosthenes
function sieve(n) {
const p = new Array(n+1).fill(true); p[0]=p[1]=false;
for (let i=2; i*i<=n; i++) if(p[i]) for(let j=i*i; j<=n; j+=i) p[j]=false;
return p;
}
Trailing Zeros
function trailingZeros(n) { let c=0; while(n>=5){n=Math.floor(n/5);c+=n;} return c; }
Practice Problems
Easy Problems
| Problem | Difficulty | Solution |
|---|---|---|
| LC 7 — Reverse Integer | Easy | |
| LC 9 — Palindrome Number | Easy | |
| LC 13 — Roman to Integer | Easy |
| LC 66 — Plus One | Easy | | | LC 69 — Sqrt(x) | Easy | |
| LC 168 — Excel Sheet Column Title | Easy | | | LC 171 — Excel Sheet Column Number | Easy | | | LC 202 — Happy Number | Easy | | | LC 231 — Power of Two | Easy | | | LC 258 — Add Digits | Easy | | | LC 263 — Ugly Number | Easy | | | LC 326 — Power of Three | Easy | | | LC 342 — Power of Four | Easy | | | LC 367 — Valid Perfect Square | Easy | | | LC 415 — Add Strings | Easy | | | LC 441 — Arranging Coins | Easy | | | LC 507 — Perfect Number | Easy | | | LC 509 — Fibonacci Number | Easy | | | LC 728 — Self Dividing Numbers | Easy | | | LC 1137 — N-th Tribonacci Number | Easy | | | LC 1175 — Prime Arrangements | Easy | | | LC 1281 — Subtract the Product and Sum of Digits | Easy | | | LC 1317 — Convert Integer to the Sum of Two No-Zero Integers | Easy | | | LC 1323 — Maximum 69 Number | Easy | | | LC 1360 — Number of Days Between Two Dates | Easy | | | CC — Add Two Numbers (FLOW001) | Easy | | | CC — Small Factorials (FLOW018) | Easy | | | CC — First and Last Digit (FLOW004) | Easy | | | CC — Sum of Digits (FLOW006) | Easy | | | CC — GCD and LCM (FLOW016) | Easy | | | CC — Prime Generator (PRIME1) | Easy | | | CC — Reverse Number (REVNUM) | Easy | |
Medium Problems
| Problem | Difficulty | Solution |
|---|---|---|
| LC 12 — Integer to Roman | Medium |
| LC 29 — Divide Two Integers | Medium | | | LC 43 — Multiply Strings | Medium | | | LC 50 — Pow(x, n) | Medium | |
| LC 166 — Fraction to Recurring Decimal | Medium | |
| LC 172 — Factorial Trailing Zeroes | Medium | | | LC 204 — Count Primes | Medium | | | LC 264 — Ugly Number II | Medium | | | LC 279 — Perfect Squares | Medium | |
| LC 319 — Bulb Switcher | Medium | | | LC 365 — Water and Jug Problem | Medium | | | LC 372 — Super Pow | Medium | |
| LC 396 — Rotate Function | Medium | | | LC 470 — Implement Rand10 Using Rand7 | Medium | | | LC 593 — Valid Square | Medium | |
| LC 633 — Sum of Square Numbers | Medium | | | LC 754 — Reach a Number | Medium | | | LC 780 — Reaching Points | Medium | | | LC 829 — Consecutive Numbers Sum | Medium | | | LC 858 — Mirror Reflection | Medium | | | LC 914 — X of a Kind in a Deck of Cards | Medium | | | LC 1006 — Clumsy Factorial | Medium | | | LC 1217 — Minimum Cost to Move Chips to The Same Position | Medium | | | LC 1390 — Four Divisors | Medium | | | CC — Fibonacci (FIBOSUM) | Medium | |
| CC — Modular Exponentiation (MODEX) | Medium | | | CC — Catalan Numbers (CATALAN) | Medium | | | CC — Number Theory (NUMTHEORY) | Medium | |
Hard Problems
Related Topics
- School Basics — primes, GCD, factorial
- Bit Manipulation — arithmetic bit tricks
← Back to Home · © sparshjaswal