Math for Interviews

🔢 Math Magic for Coding Interviews

The Secret Toolkit Every Programmer Needs

Imagine you’re a wizard with a magic calculator. But this isn’t any calculator—it can find common factors in a blink, test if numbers are special, and compute huge powers in seconds! Today, we’ll unlock these superpowers.

🎯 The Big Picture

Think of math in coding like kitchen tools. You don’t need every gadget, but having the right ones makes cooking (coding) SO much easier:

1️⃣ GCD and LCM: Finding Common Ground

What’s GCD?

GCD = Greatest Common Divisor

Imagine you have 12 cookies and 18 candies. You want to share them equally among friends with NO leftovers. What’s the BIGGEST group you can make?

# 12 can be split: 1, 2, 3, 4, 6, 12 friends
# 18 can be split: 1, 2, 3, 6, 9, 18 friends
# Common options: 1, 2, 3, 6
# Biggest common: 6 friends!

# GCD(12, 18) = 6

What’s LCM?

LCM = Least Common Multiple

Two buses leave a station. Bus A comes every 4 minutes. Bus B comes every 6 minutes. When will BOTH buses be at the station together again?

# Bus A: 4, 8, 12, 16, 20, 24...
# Bus B: 6, 12, 18, 24...
# First match: 12 minutes!

# LCM(4, 6) = 12

The Magic Formula

LCM(a, b) = (a × b) ÷ GCD(a, b)

Example:

# GCD(4, 6) = 2
# LCM(4, 6) = (4 × 6) ÷ 2 = 24 ÷ 2 = 12 ✓

2️⃣ Euclidean Algorithm: The Fast GCD Finder

The Old Way (Slow)

List all factors of both numbers. Find common ones. Pick biggest.

For big numbers? Nightmare! 🙈

The Smart Way: Euclid’s Trick

Euclid discovered something 2000 years ago:

GCD(a, b) = GCD(b, a % b)

Keep replacing until one number becomes 0!

Step-by-Step Example

Find GCD(48, 18):

Step 1: GCD(48, 18)
        48 % 18 = 12
        → GCD(18, 12)

Step 2: GCD(18, 12)
        18 % 12 = 6
        → GCD(12, 6)

Step 3: GCD(12, 6)
        12 % 6 = 0
        → GCD(6, 0)

Answer: 6! 🎉

Python Code

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Test it!
print(gcd(48, 18))  # Output: 6

Why It Works

Think of it like cutting rope:

• You have 48cm and 18cm ropes
• Cut as many 18cm pieces from 48cm as you can
• Leftover: 12cm
• Now cut 12cm pieces from 18cm
• Leftover: 6cm
• Cut 6cm pieces from 12cm
• Leftover: 0!
• 6cm is the magic length that fits both!

3️⃣ Prime Numbers: The Atoms of Math

What Makes a Number Prime?

A prime number is like a LEGO brick that can’t be broken down further.

• 7 is prime → Only 1 and 7 divide it evenly
• 12 is NOT prime → 2 × 6 = 12, 3 × 4 = 12

The First Few Primes

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

🎯 Fun Fact: 2 is the ONLY even prime!

How to Check if a Number is Prime

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # Only check odd numbers up to √n
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

Why Only Check Up to √n?

If n = a × b, then one of them must be ≤ √n.

Example: Is 36 prime?

• √36 = 6
• Check: 2? Yes, 36 ÷ 2 = 18
• Not prime! Found it early!

4️⃣ Sieve of Eratosthenes: The Prime Factory

The Problem

Finding ONE prime is easy. Finding ALL primes up to 1,000,000?

Checking each number individually = TOO SLOW! 🐌

The Clever Solution

Imagine a classroom with 100 students (numbered 2-100).

1. Student 2 stands up → “I’m prime!”
2. All multiples of 2 sit down (4, 6, 8…)
3. Next standing student (3) stands up → “I’m prime!”
4. All multiples of 3 sit down (6, 9, 12…)
5. Continue until everyone is either standing (prime) or sitting (not prime)!

Visual Representation

Start: 2  3  4  5  6  7  8  9  10 ...

After 2: 2  3  X  5  X  7  X  9  X  ...
         ✓     sit    sit    sit

After 3: 2  3  X  5  X  7  X  X  X  ...
         ✓  ✓           ✓     sit

Primes: 2, 3, 5, 7, 11, 13...

Python Code

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    p = 2
    while p * p <= n:
        if is_prime[p]:
            # Mark multiples as not prime
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1

    # Collect all primes
    return [i for i in range(n + 1) if is_prime[i]]

print(sieve(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Why Start from p × p?

All smaller multiples were already crossed out!

• 3 × 2 was crossed when we did 2’s multiples
• Start at 3 × 3 = 9

5️⃣ Modular Arithmetic: Clock Math

The Clock Analogy

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

10 + 5 = 15... but clocks show 3!
15 % 12 = 3 ✓

This is modular arithmetic!

The Notation

a % n  or  a mod n

Means: “What’s the remainder when a is divided by n?”

Key Properties

# Addition
(a + b) % n = ((a % n) + (b % n)) % n

# Multiplication
(a × b) % n = ((a % n) × (b % n)) % n

# Example: (7 + 8) % 5
# Method 1: 15 % 5 = 0
# Method 2: (7%5 + 8%5) % 5
#         = (2 + 3) % 5 = 0 ✓

Why It Matters in Coding

Big numbers can overflow! Modular arithmetic keeps them small.

# Calculate (123456789 × 987654321) % 1000000007
# Direct multiplication = HUGE number!
# With mod: Keep it manageable

a = 123456789 % 1000000007
b = 987654321 % 1000000007
result = (a * b) % 1000000007
# Safe and correct!

Common Modulo Values

6️⃣ Fast Exponentiation: Power in a Flash

The Problem

Calculate 2^100.

Slow way: Multiply 2 × 2 × 2 × 2… (100 times)

Time: 100 operations 😴

The Fast Way: Binary Magic

Instead of 100 multiplications, use only ~7!

Key Insight:

2^100 = 2^64 × 2^32 × 2^4
      = (((2^2)^2)^2)^2... (just keep squaring!)

The Algorithm

def fast_power(base, exp, mod):
    result = 1
    base = base % mod

    while exp > 0:
        # If exp is odd, multiply result
        if exp % 2 == 1:
            result = (result * base) % mod

        # Square the base
        base = (base * base) % mod

        # Divide exp by 2
        exp = exp // 2

    return result

# 2^10 mod 1000
print(fast_power(2, 10, 1000))  # 24

Step-by-Step: 2^13

13 in binary: 1101
13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0

So: 2^13 = 2^8 × 2^4 × 2^1
         = 256 × 16 × 2
         = 8192 ✓

Visual Breakdown

exp=13 (odd)  → result = 1 × 2 = 2
base = 2² = 4, exp = 6

exp=6 (even)  → result stays 2
base = 4² = 16, exp = 3

exp=3 (odd)   → result = 2 × 16 = 32
base = 16² = 256, exp = 1

exp=1 (odd)   → result = 32 × 256 = 8192
base = 256², exp = 0

DONE! Answer: 8192

Time Comparison

From millions to just 20! 🚀

🧩 How They All Connect

graph TD
    A["Number Theory"] --> B["GCD/LCM"]
    A --> C["Prime Numbers"]
    A --> D["Modular Math"]

    B --> E["Euclidean Algorithm"]
    C --> F["Sieve of Eratosthenes"]
    D --> G["Fast Exponentiation"]

    E --> H["Fraction Simplification"]
    F --> I["Prime Factorization"]
    G --> J["Cryptography"]

🎯 Interview Cheat Codes

🏆 You Did It!

You now have 6 powerful math tools in your coding toolkit:

1. ✅ GCD/LCM - Find common factors and multiples
2. ✅ Euclidean Algorithm - Lightning-fast GCD
3. ✅ Prime Numbers - Understand the atoms of math
4. ✅ Sieve - Generate primes like a factory
5. ✅ Modular Math - Handle huge numbers safely
6. ✅ Fast Exponentiation - Compute powers in log time

Go crush those coding interviews! 💪🎉