Math for Interviews

Math for Interviews: Your Secret Weapon

The Story: Finding Common Ground

Imagine you and your friend are sharing pizza slices. You have 12 slices, they have 18. What’s the biggest number of slices you can make into equal groups? That’s exactly what GCD does!

And what if you both want to clap at the same time? You clap every 4 seconds, they clap every 6 seconds. When will you clap together? That’s LCM!

Let’s unlock these powerful math tools that interviewers love to ask about!

1. GCD and LCM: The Best Friends

GCD (Greatest Common Divisor)

What is it? The biggest number that divides both numbers evenly.

Think of it like this: You have 12 apples and 18 oranges. You want to make gift bags with the same number of each fruit in every bag. The biggest bag size? 6 items!

// Simple GCD using Euclidean method
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Example: gcd(12, 18) = 6

LCM (Least Common Multiple)

What is it? The smallest number that both numbers divide into evenly.

Like two runners on a track. One takes 4 minutes per lap, one takes 6 minutes. They’ll meet at the start after 12 minutes!

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

// Example: lcm(4, 6) = 12

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

2. Euclidean Algorithm: The Smart Way

The Old Way (Slow)

Check every number from 1 to the smallest. Boring and slow!

The Smart Way (Euclidean)

Here’s the trick: GCD(a, b) = GCD(b, a % b)

graph TD
    A["GCD#40;48, 18#41;"] --> B["48 % 18 = 12"]
    B --> C["GCD#40;18, 12#41;"]
    C --> D["18 % 12 = 6"]
    D --> E["GCD#40;12, 6#41;"]
    E --> F["12 % 6 = 0"]
    F --> G["Answer: 6!"]

Why does it work?

• If b divides a evenly, then b is the GCD
• Otherwise, the GCD of a and b equals GCD of b and the remainder

// Recursive (elegant)
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Iterative (interview-safe)
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Time Complexity: O(log(min(a, b))) - Super fast!

3. Prime Numbers: The Building Blocks

What Makes a Number Prime?

A prime number is like a stubborn friend - it only divides by 1 and itself. No other friends allowed!

• 2 is prime (only 1 × 2)
• 4 is NOT prime (2 × 2)
• 7 is prime (only 1 × 7)

boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i+2) == 0)
            return false;
    }
    return true;
}

Why check only up to √n?

If n = a × b, one of them must be ≤ √n. So we only need to check that far!

4. Sieve of Eratosthenes: Finding ALL Primes

The Story

Imagine you have 100 kids in line. You want to find the special ones (primes).

1. Cross out 1 (not prime)
2. Keep 2, cross out all its friends (4, 6, 8…)
3. Keep 3, cross out all its friends (6, 9, 12…)
4. Continue until you’ve found all special kids!

graph TD
    A["Start: 2,3,4,5,6,7,8,9,10"] --> B["Keep 2, remove 4,6,8,10"]
    B --> C["2,3,5,7,9"]
    C --> D["Keep 3, remove 9"]
    D --> E["2,3,5,7"]
    E --> F["All primes found!"]

boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

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

Time: O(n log log n) - Almost linear!

Space: O(n) - Array of booleans

5. Modular Arithmetic: Clock Math

The Clock Analogy

What’s 15 o’clock? It’s 3 o’clock! The clock “wraps around” after 12.

That’s modular arithmetic: 15 % 12 = 3

Key Properties

// Safe modular addition (avoids overflow)
long modAdd(long a, long b, long m) {
    return ((a % m) + (b % m)) % m;
}

// Safe modular multiplication
long modMul(long a, long b, long m) {
    return ((a % m) * (b % m)) % m;
}

Why is this useful?

When numbers get HUGE, modular arithmetic keeps them small!

6. Fast Exponentiation: Power in a Flash

The Problem

Calculate 2^1000. That’s a HUGE number!

The Slow Way

Multiply 2 by itself 1000 times. Takes 1000 steps.

The Fast Way (Binary Exponentiation)

Use the magic of squaring!

• 2^8 = 2^4 × 2^4 (only need to calculate 2^4 once!)
• 2^4 = 2^2 × 2^2
• 2^2 = 2 × 2

Only ~10 steps for 2^1000!

graph TD
    A["2^10"] --> B["Is 10 even? Yes!"]
    B --> C["2^10 = #40;2^5#41;^2"]
    C --> D["Is 5 odd? Yes!"]
    D --> E["2^5 = 2 × #40;2^2#41;^2"]
    E --> F["2^2 = 4"]
    F --> G["2^5 = 2 × 16 = 32"]
    G --> H["2^10 = 32^2 = 1024"]

// Fast power with modulo
long power(long base, long exp, long mod) {
    long result = 1;
    base %= mod;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp /= 2;
        base = (base * base) % mod;
    }
    return result;
}

// Example: power(2, 10, 1000) = 24

Time: O(log n) instead of O(n)!

Interview Patterns

Pattern 1: GCD/LCM Problems

// LCM of array
long lcmOfArray(int[] arr) {
    long result = arr[0];
    for (int i = 1; i < arr.length; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}

Pattern 2: Modular Inverse

When you need to divide in modular arithmetic:

// a^(-1) mod m = a^(m-2) mod m
// (Only works when m is prime!)
long modInverse(long a, long m) {
    return power(a, m - 2, m);
}

Pattern 3: Count Divisors

int countDivisors(int n) {
    int count = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            count++; // i is a divisor
            if (i != n / i) count++; // n/i too
        }
    }
    return count;
}

Quick Reference

Your Confidence Checklist

• [ ] I can calculate GCD using the Euclidean algorithm
• [ ] I understand why LCM = a×b / GCD
• [ ] I can check if a number is prime efficiently
• [ ] I can generate all primes using the Sieve
• [ ] I know when to use modular arithmetic
• [ ] I can calculate large powers quickly

You’ve got this! These are the building blocks that unlock countless interview problems. Practice each one, and you’ll handle any math question with confidence!