Math for Interviews

🧙‍♂️ The Magic Number Kitchen: Math for Interviews

Imagine you’re a chef in a magical kitchen where numbers are your ingredients. Today, we’ll learn the secret recipes that make coding interviews feel like cooking with friends!

🍕 Chapter 1: GCD and LCM — Finding the Perfect Slice

The Pizza Party Problem

You have 12 slices of pizza and 8 cups of juice. You want to divide them equally among friends so nobody fights. What’s the biggest group that gets equal shares of both?

That’s the GCD — the Greatest Common Divisor!

GCD = The biggest number that can divide two numbers perfectly (no leftovers!)

Finding GCD: The Sharing Game

// GCD of 12 and 8
// Factors of 12: 1, 2, 3, 4, 6, 12
// Factors of 8: 1, 2, 4, 8
// Common: 1, 2, 4
// Greatest: 4! ✨

function gcd(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}
console.log(gcd(12, 8)); // 4

LCM: The Sync-Up Number

Now imagine two dancers. One spins every 3 seconds, another every 4 seconds. When do they both spin at the same time?

LCM = The smallest number both can divide into!

// LCM of 3 and 4 = 12
// 3: 3, 6, 9, 12, 15...
// 4: 4, 8, 12, 16...
// First match: 12! 🎯

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}
console.log(lcm(3, 4)); // 12

Magic Formula: LCM(a,b) = (a × b) / GCD(a,b)

graph TD
    A["Two Numbers"] --> B["Find GCD"]
    B --> C["GCD = Biggest shared divisor"]
    A --> D["Find LCM"]
    D --> E["LCM = Smallest shared multiple"]
    C --> F["LCM = a×b / GCD"]

🪜 Chapter 2: Euclidean Algorithm — The Subtraction Dance

The Ancient Greek Shortcut

A Greek mathematician named Euclid discovered a clever trick 2000 years ago!

Instead of listing all factors, he said: “Keep subtracting the smaller from the bigger until they’re equal!”

Even faster: “Use remainders instead of subtracting!”

The Dance Steps

// GCD(48, 18) using Euclid's method
// Step 1: 48 ÷ 18 = 2 remainder 12
// Step 2: 18 ÷ 12 = 1 remainder 6
// Step 3: 12 ÷ 6 = 2 remainder 0
// STOP! GCD = 6 🎉

function euclidGCD(a, b) {
  if (b === 0) return a;
  return euclidGCD(b, a % b);
}
console.log(euclidGCD(48, 18)); // 6

Why It Works (The Cookie Explanation)

Imagine you have 48 cookies and want to pack them in boxes of 18.

• After filling 2 boxes, you have 12 cookies left
• Now try packing 18 in boxes of 12 → 1 box, 6 left
• Pack 12 in boxes of 6 → 2 boxes, 0 left!
• The box size 6 is your GCD!

graph TD
    A["48, 18"] -->|48 mod 18 = 12| B["18, 12"]
    B -->|18 mod 12 = 6| C["12, 6"]
    C -->|12 mod 6 = 0| D["GCD = 6 ✨"]

⭐ Chapter 3: Prime Numbers — The Atomic Building Blocks

What Makes a Number Special?

A prime number is like a LEGO brick that can’t be broken into smaller LEGO pieces.

Prime = A number greater than 1 that only divides by 1 and itself!

The VIP list: 2, 3, 5, 7, 11, 13, 17, 19, 23…

Not invited: 4 (2×2), 6 (2×3), 9 (3×3)…

The Prime Checker

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) {
    return false;
  }
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
  return true;
}
console.log(isPrime(17)); // true ⭐
console.log(isPrime(18)); // false

The Square Root Secret

Why check only up to √n?

If a number has a factor bigger than its square root, the matching factor must be smaller! So we only need to check the little ones.

For 36: √36 = 6. We only check 2, 3, 4, 5, 6!

🔮 Chapter 4: Sieve of Eratosthenes — The Magic Filter

The Ancient Greek Strainer

Eratosthenes invented a genius trick to find ALL primes up to any number!

Think of it like a kitchen strainer that catches all the non-primes:

1. Write numbers 2 to N
2. Circle 2 (first prime), cross out all multiples: 4, 6, 8…
3. Circle 3 (next uncrossed), cross out multiples: 6, 9, 12…
4. Keep going until done!

The Code Recipe

function sieve(n) {
  let isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  let primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}
console.log(sieve(30));
// [2,3,5,7,11,13,17,19,23,29]

graph TD
    A["Numbers 2-20"] --> B["Cross out 2's multiples]
    B --> C[Cross out 3's multiples"]
    C --> D[Cross out 5's multiples]
    D --> E["Primes: 2,3,5,7,11,13,17,19"]

Why Start at i×i?

When crossing out multiples of 5, we start at 25 (5×5), not 10 or 15. Why?

Because 10 = 2×5 (already crossed by 2) and 15 = 3×5 (already crossed by 3)!

🎡 Chapter 5: Modular Arithmetic — The Clock Math

The 12-Hour Clock Rule

What time is it 5 hours after 10 o’clock?

Not 15! The clock wraps around to 3.

That’s modular arithmetic! Numbers wrap around after reaching a limit.

10 + 5 = 15 ≡ 3 (mod 12)

The Magic Mod Operator

// The % operator gives the remainder
console.log(15 % 12); // 3
console.log(25 % 7);  // 4
console.log(100 % 10); // 0

// Useful patterns:
// n % 2 === 0 → n is even
// n % 2 === 1 → n is odd

Mod Rules (The Cheat Codes)

// Addition Rule
(a + b) % m === ((a % m) + (b % m)) % m

// Multiplication Rule
(a * b) % m === ((a % m) * (b % m)) % m

// Example: (7 + 8) % 5
// = (7 % 5 + 8 % 5) % 5
// = (2 + 3) % 5 = 0 ✓

Why Programmers Love Mod

• Wrap around arrays: index % array.length
• Check divisibility: n % 3 === 0
• Keep numbers small: Prevent overflow in big calculations!

⚡ Chapter 6: Fast Exponentiation — The Power Shortcut

The Slow Way vs The Fast Way

What’s 2^10?

Slow: 2×2×2×2×2×2×2×2×2×2 = 10 multiplications 😴

Fast: Use a magic trick! Only 4 multiplications needed! 🚀

The Binary Power Trick

The secret: Square and multiply based on binary!

// 2^10 the fast way
// 10 in binary = 1010
// 2^10 = 2^8 × 2^2 = 256 × 4 = 1024

function fastPow(base, exp) {
  let result = 1;
  while (exp > 0) {
    if (exp % 2 === 1) {
      result *= base;
    }
    base *= base;
    exp = Math.floor(exp / 2);
  }
  return result;
}
console.log(fastPow(2, 10)); // 1024

With Modular Arithmetic (Interview Favorite!)

function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;

  while (exp > 0) {
    if (exp % 2 === 1) {
      result = (result * base) % mod;
    }
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}
// 2^100 mod 1000000007
console.log(modPow(2, 100, 1000000007));
// 976371285

graph TD
    A["2^10"] --> B["exp=10, base=2, result=1"]
    B -->|10 is even| C["exp=5, base=4, result=1"]
    C -->|5 is odd| D["exp=2, base=16, result=4"]
    D -->|2 is even| E["exp=1, base=256, result=4"]
    E -->|1 is odd| F["result = 4×256 = 1024 ✨"]

Why It’s O(log n)

Each step, we halve the exponent. For 2^1000, we only need about 10 steps instead of 1000!

🎯 Quick Reference Table

🏆 You Made It!

You now have 6 powerful tools in your interview toolkit:

1. GCD/LCM — For sharing and syncing problems
2. Euclidean Algorithm — The ancient speed hack
3. Prime Numbers — The building blocks
4. Sieve — Mass prime production
5. Modular Arithmetic — Keep numbers manageable
6. Fast Exponentiation — Exponential without the wait

Remember: Every expert was once a beginner. Practice these recipes, and soon you’ll be cooking up solutions faster than ever! 🚀