Math & Number Theory

1. Introduction: The Universal Language

While most technical interviews focus on Data Structures (like Trees and Maps), a subset of problems tests your fundamental mathematical intuition. Can you find the Greatest Common Divisor? Can you determine if a number is Prime? Can you prevent a massive calculation from causing an Integer Overflow?

Understanding Number Theory is crucial for cryptography, hashing algorithms, and solving competitive programming problems. If you don't know the mathematical tricks, you will often find yourself writing $O(N)$ brute-force loops that immediately fail the time limits, whereas the optimal mathematical solution executes in $O(\log N)$ or even $O(1)$ time.

2. Core Concept: Primality and GCD

Two of the most foundational math concepts in coding are:

1. Prime Numbers: Numbers greater than 1 that have exactly two factors: 1 and themselves.
2. Greatest Common Divisor (GCD): The largest positive integer that divides two numbers without a remainder.

The Square Root Optimization

When checking if a number $N$ is prime, you don't need to check all numbers from $2$ to $N-1$. Factors always appear in pairs. If $A \times B = N$, one of those factors must be $\le \sqrt{N}$ and the other must be $\ge \sqrt{N}$. Therefore, you only need to check divisibility up to $\lfloor\sqrt{N}\rfloor$. This optimization drops the time complexity from $O(N)$ to $O(\sqrt{N})$.

3. Beginner Code Example: Basic Prime Check and GCD

Problem Statement 1: Write a function to check if a number is prime.

public class PrimeMath {
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        
        // Skip even numbers and multiples of 3 for minor optimization
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        // Only check up to the square root of n!
        // We write i * i <= n to avoid using the slow Math.sqrt() function
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

Problem Statement 2: Find the GCD of two numbers using the Euclidean Algorithm. The Insight: The Euclidean algorithm states that GCD(A, B) == GCD(B, A % B). This recursively shrinks the numbers incredibly fast!

public class GCDMath {
    // O(log(min(a, b))) time complexity
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    
    // LCM (Least Common Multiple) uses the GCD!
    public static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b; // Divide first to prevent integer overflow
    }
}

4. Intermediate Code Example: Sieve of Eratosthenes

Problem Statement: (LeetCode 204) Count Primes. Given an integer $N$, return the number of prime numbers that are strictly less than $N$.

If we run our $O(\sqrt{N})$ isPrime function for every number from $1$ to $N$, the total time is $O(N \sqrt{N})$, which is too slow for large $N$.

The Insight: Use the Sieve of Eratosthenes. Create a boolean array from $0$ to $N$. Assume everything is prime. Start at 2. Since 2 is prime, mathematically, all multiples of 2 (4, 6, 8, 10...) CANNOT be prime! Cross them out. Move to 3. It's prime. Cross out 6, 9, 12... This crosses out composites massively in bulk!

public class SieveOfEratosthenes {
    public static int countPrimes(int n) {
        if (n <= 2) return 0;
        
        boolean[] isPrime = new boolean[n];
        // Assume all are prime initially
        for (int i = 2; i < n; i++) isPrime[i] = true;
        
        // We only need to sieve up to the square root of n!
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                // Cross out all multiples of i, starting from i^2
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Count remaining primes
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        
        return count;
    }
}

Complexity Analysis:

• Time Complexity: $O(N \log(\log N))$. This is practically $O(N)$ for all reasonable values of $N$.
• Space Complexity: $O(N)$ for the boolean array.

5. Advanced Code Example: Modulo Arithmetic & Fast Exponentiation

Problem Statement: (LeetCode 50) Implement pow(x, n), which calculates x raised to the power n ($x^n$).

If you use a loop for(int i=0; i<n; i++), it takes $O(N)$ time. If $n = 2^{31} - 1$, your program will freeze.

The Insight: Binary Exponentiation. $x^{10} = (x^5)^2$. $x^5 = x \cdot (x^2)^2$. By dividing the power by 2 at each step, we can calculate massive powers in $O(\log N)$ time!

public class FastPower {
    public static double myPow(double x, int n) {
        // Handle negative powers and prevent integer overflow of Integer.MIN_VALUE
        long N = n; 
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        
        double result = 1.0;
        double currentProduct = x;
        
        while (N > 0) {
            // If the current power is ODD, multiply the result by current product
            if (N % 2 == 1) {
                result = result * currentProduct;
            }
            // Square the product and halve the power!
            currentProduct = currentProduct * currentProduct;
            N /= 2;
        }
        
        return result;
    }
}

6. Common Mistakes Beginners Make

1. Integer Overflow on Integer.MIN_VALUE

   • The Mistake: int N = -n; where n is -2147483648.
   • Why it's wrong: The 32-bit signed integer limit is -2147483648 to 2147483647. You cannot mathematically make the minimum value positive within an int. It overflows and remains negative!
   • The Fix: Always cast to a long before flipping the sign of a parameter. long N = n; if (N < 0) N = -N;.

2. Forgetting Modulo Distribution Rules

   • The Mistake: (A + B) % M = (A % M) + (B % M)
   • Why it's wrong: The result of the addition could exceed M!
   • The Fix: (A + B) % M = ((A % M) + (B % M)) % M. You must apply the modulo to the final result as well. (This applies to multiplication too).

3. Starting the inner loop of the Sieve at j = i * 2

   • The Mistake: for (int j = i * 2; j < n; j += i)
   • Why it's wrong: While technically correct, it's inefficient. If i = 5, then 5 * 2 = 10. But 10 was already crossed out when i = 2! 5 * 3 = 15 was crossed out when i = 3.
   • The Fix: The inner loop should strictly start at j = i * i. Everything below that has already been crossed out by smaller primes!

7. Interview Q&A

Q1: How do you generate all divisors of a number efficiently? Answer: Iterate i from $1$ up to $\sqrt{N}$. If N % i == 0, then i is a divisor, AND N / i is also a divisor! Add both to your list (being careful not to add the square root twice if it's a perfect square). Time complexity $O(\sqrt{N})$.

Q2: What is the "Pigeonhole Principle"? Answer: If you have $N$ boxes and $N+1$ pigeons, at least one box must contain multiple pigeons. This is wildly useful in array problems. For example, if an array has $N+1$ integers, and all integers are in the range $[1, N]$, there MUST be a duplicate! (LeetCode 287 - Find the Duplicate Number).

Q3: Why are large prime numbers used in Hashing and Cryptography? Answer: Modulo arithmetic with prime numbers evenly distributes values across the hash table, drastically reducing collisions compared to composite numbers. In cryptography (RSA), multiplying two massive primes is easy, but factoring the resulting number back into the original primes is currently impossible to do in reasonable time (unless P=NP or Quantum computing scales).

8. Practice Problems

1. Count Primes (LeetCode 204)
   • Goal: Master the Sieve of Eratosthenes.
2. Pow(x, n) (LeetCode 50)
   • Goal: Master $O(\log N)$ Binary Exponentiation.
3. Find the Duplicate Number (LeetCode 287)
   • Hint: Pigeonhole principle proves a duplicate exists. Use Fast/Slow pointers (Floyd's algorithm) to find it!

9. Summary

• Primes & Divisors: Only loop up to $\sqrt{N}$.
• Sieve of Eratosthenes: The most efficient way to generate primes in bulk. Time complexity $O(N \log \log N)$.
• GCD: Use the Euclidean Algorithm: gcd(a, b) { return b == 0 ? a : gcd(b, a % b); }.
• Fast Power: Halve the power and square the base at each step to drop exponentiation to $O(\log N)$.