All Roadmaps›🧠 Data Structures & Algorithms›Phase 1›Math for DSA (Logarithms, Powers, Modular Arithmetic)

Math for DSA (Logarithms, Powers, Modular Arithmetic)

0/12 in this phase0/57 across the roadmap

📖 Concept

Mathematics is the backbone of algorithm analysis. You don't need a math degree, but you MUST understand these concepts to analyze complexity and solve problems.

Logarithms (log):

  • log₂(n) = "how many times can you halve n before reaching 1?"
  • log₂(8) = 3, log₂(1024) = 10, log₂(1,000,000) ≈ 20
  • Every time you see "halving" in an algorithm → O(log n)
  • Binary search, balanced BST operations, merge sort recursion depth

Powers of 2:

  • 2¹⁰ = 1,024 ≈ 1 thousand
  • 2²⁰ ≈ 1 million, 2³⁰ ≈ 1 billion
  • If input ≤ 2²⁰, O(n²) still works. If input ≤ 2³⁰, you need O(n) or O(n log n)

Modular Arithmetic:

  • (a + b) % m = ((a % m) + (b % m)) % m
  • Used in: hashing, cyclic buffers, round-robin, clock arithmetic
  • Preventing integer overflow in competitive programming

Arithmetic & Geometric Series:

  • 1+2+3+...+n = n(n+1)/2 → O(n²) — this is why nested loops are quadratic
  • 1+2+4+...+n = 2n-1 → O(n) — this is why doubling in dynamic arrays gives O(n) total

Floor, Ceil, and Integer Division:

  • Math.floor(7/2) = 3, Math.ceil(7/2) = 4
  • Used everywhere: binary search midpoint, partitioning, pagination

🏠 Real-world analogy: Logarithms are like the number of digits in a number — 1000 has 4 digits (log₁₀(1000)=3). Doubling your money is exponential; it takes logarithmic time to reach a goal.

💻 Code Example

codeTap to expand ⛶
1// LOGARITHM INTUITION
2// How many times can you divide n by 2?
3function log2(n) {
4  let count = 0;
5  while (n > 1) {
6    n = Math.floor(n / 2);
7    count++;
8  }
9  return count; // This IS log₂(n)
10}
11console.log(log2(1024)); // 10
12console.log(log2(1000000)); // ~20
13

14// MODULAR ARITHMETIC
15// Useful for hashing, cyclic operations
16function circularIndex(index, size) {
17  return ((index % size) + size) % size; // Handles negative!
18}
19console.log(circularIndex(-1, 5)); // 4 (wraps around)
20console.log(circularIndex(7, 5));  // 2
21

22// Modular exponentiation (prevents overflow)
23function modPow(base: number, exp: number, mod: number): number {
24  let result = 1;
25  base = base % mod;
26  while (exp > 0) {
27    if (exp % 2 === 1) result = (result * base) % mod;
28    exp = Math.floor(exp / 2);
29    base = (base * base) % mod;
30  }
31  return result;
32}
33

34// ARITHMETIC SERIES — why nested loops are O(n²)
35// 1 + 2 + 3 + ... + n = n(n+1)/2
36function sumOfSeries(n) {
37  return n * (n + 1) / 2;
38}
39// This proves: for(i=0;i<n;i++) for(j=0;j<i;j++) → n(n-1)/2 ≈ n²/2 = O(n²)
40

41// GCD — Euclidean Algorithm
42function gcd(a, b) {
43  while (b !== 0) {
44    [a, b] = [b, a % b];
45  }
46  return a;
47}
48// Time: O(log(min(a,b))) — very efficient!
49

50// PRIME CHECK — O(√n)
51function isPrime(n: number): boolean {
52  if (n < 2) return false;
53  if (n < 4) return true;
54  if (n % 2 === 0 || n % 3 === 0) return false;
55  for (let i = 5; i * i <= n; i += 6) {
56    if (n % i === 0 || n % (i + 2) === 0) return false;
57  }
58  return true;
59}
60

61// SIEVE OF ERATOSTHENES — all primes up to n
62function sieve(n: number): number[] {
63  const isPrime = new Array(n + 1).fill(true);
64  isPrime[0] = isPrime[1] = false;
65  for (let i = 2; i * i <= n; i++) {
66    if (isPrime[i]) {
67      for (let j = i * i; j <= n; j += i) {
68        isPrime[j] = false;
69      }
70    }
71  }
72  return isPrime.reduce((primes, val, idx) => {
73    if (val) primes.push(idx);
74    return primes;
75  }, []);
76}

🏋️ Practice Exercise

Practice Problems:

  1. Calculate log₂(n) without using Math.log — use a while loop
  2. Prove that 1+2+4+8+...+n = 2n-1 and explain why dynamic array resize is O(n) total
  3. Implement modular exponentiation: (base^exp) % mod efficiently
  4. Write a function to find GCD of two numbers using Euclidean algorithm
  5. Check if a number is prime in O(√n) time
  6. Generate all primes up to n using Sieve of Eratosthenes
  7. Explain why Math.floor((low+high)/2) can overflow and how to fix it
  8. Implement fast integer square root without Math.sqrt
  9. Calculate nCr (combinations) using modular arithmetic
  10. Why is log₂(n) = log₁₀(n) / log₁₀(2) and why doesn't the base matter in Big-O?

⚠️ Common Mistakes

  • Integer overflow when computing (low + high) / 2 — use low + (high - low) / 2 or (low + high) >>> 1

  • Forgetting that in Big-O, log base doesn't matter — log₂(n), log₃(n), log₁₀(n) all differ by a constant factor

  • Not recognizing the arithmetic series pattern — if inner loop runs 1+2+3+...+n times, that's O(n²), not O(n)

  • Using floating-point math for integer problems — leads to precision errors; use integer arithmetic

  • Not knowing that √n iterations is O(√n), which is between O(log n) and O(n) — used in prime checks and some optimizations

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Math for DSA (Logarithms, Powers, Modular Arithmetic)

← PreviousIteration vs RecursionNext →Bit Manipulation Basics