Math for Coding Interviews

In simple words

A handful of math tricks show up again and again: GCD, prime numbers, modulo arithmetic and fast power. The focus here is on writing them cleanly and safely in Java.

Key ideas

• GCD (Euclid): gcd(a, b) = gcd(b, a % b), stop when b = 0. O(log min(a,b)). LCM = a / gcd(a,b) × b.
• Is n prime? Check divisors only up to √n → O(√n).
• Sieve of Eratosthenes: all primes up to n in O(n log log n).
• Modulo 10⁹+7: large answers are asked 'mod M'. Apply mod after every add/multiply, use long for the multiply.
• Negative mod in Java: -7 % 3 == -1. Use Math.floorMod(a, m) or ((a % m) + m) % m.
• Digits: n % 10 gives the last digit, n / 10 removes it.
• nCr with Pascal's triangle: C(n, r) = C(n−1, r−1) + C(n−1, r).

Operations & cost

Java code

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

boolean[] sieve(int n) {             // true = composite
    boolean[] notPrime = new boolean[n + 1];
    for (int i = 2; (long) i * i <= n; i++)
        if (!notPrime[i])
            for (int j = i * i; j <= n; j += i) notPrime[j] = true;
    return notPrime;
}

static final int MOD = 1_000_000_007;
long modPow(long base, long exp, long mod) {
    long result = 1; base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Interview traps to remember

• Reverse Integer (LeetCode 7): check for overflow before rev * 10 + d.
• Pow(x, n) (LeetCode 50): -n overflows when n == Integer.MIN_VALUE. Store n in a long.
• Negative modulo: in Java -7 % 3 == -1. Use Math.floorMod(-7, 3) to get 2.
• Why 10⁹+7: it's prime (division via Fermat inverse a^M-2), a + b fits in an int, and a × b fits in a long.
• Doubles: 0.1 + 0.2 == 0.3 is false. Compare with Math.abs(a - b) < 1e-9.
• Safe math: Math.addExact / Math.multiplyExact throw instead of silently overflowing.
• Trailing zeros of n! (LeetCode 172): count factors of 5: n/5 + n/25 + n/125 + …

Fast power (binary exponentiation)

long power(long base, long exp, long M) {
    long res = 1;
    base %= M;
    while (exp > 0) {
        if ((exp & 1) == 1) res = res * base % M;
        base = base * base % M;   // square
        exp >>= 1;                // halve
    }
    return res;                   // O(log exp)
}

Spot it when

• 'Return the answer modulo 10⁹+7' → the answer is huge; keep taking mod.
• 'Count primes', 'divisible by', 'digits of a number'.

Practice problems

Interview tip

★ In "reverse integer" style problems, check for overflow before multiplying by 10. Interviewers watch for that edge case.