Lesson 39.2 · Math for Coding Interviews

Modular Arithmetic, Fast Power and nCr

Reduce after every + and ×. Exponentiate by squaring in O(log e). Divide by multiplying with the modular inverse a^(p − 2) when p is prime.

16 min

Think of it like this

A 12-hour clock: 9 + 5 is 2 o'clock. You can add hours, multiply hours, even raise to powers, and as long as you keep wrapping at 12 you never need big numbers.

1.The rules

(a + b) mod p and (a × b) mod p can be reduced at every step. With p = 10⁹ + 7, a product of two reduced values is below 10¹⁸, which fits in a long (not an int). Subtraction: add p before taking mod so the result isn't negative.

Fast power: aᵉ = (a²)^(e/2) when e is even, × a when odd: about log₂ e multiplications.

Division: there's no "mod divide", but if p is prime, a^(p − 2) is a's inverse (Fermat's little theorem), so a / b ≡ a × b^(p − 2). Precompute factorials and inverse factorials to get C(n, r) = n! / (r! (n − r)!) in O(1) per query.

Main.java

public class Main {
    static final long P = 1_000_000_007L;

    static long power(long b, long e) {
        long r = 1;
        b %= P;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % P;
            b = b * b % P;
            e >>= 1;
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println("2^30 mod p = " + power(2, 30));
        long inv2 = power(2, P - 2);
        System.out.println("inverse of 2 = " + inv2);
        System.out.println("2 * inverse(2) mod p = " + 2 * inv2 % P);

        int n = 100;
        long[] fact = new long[n + 1], inv = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % P;
        inv[n] = power(fact[n], P - 2);
        for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % P;
        System.out.println("C(10, 3) = " + fact[10] * inv[3] % P * inv[7] % P);
        System.out.println("C(100, 50) mod p = " + fact[100] * inv[50] % P * inv[50] % P);
    }
}

Output

2^30 mod p = 73741817
inverse of 2 = 500000004
2 * inverse(2) mod p = 1
C(10, 3) = 120
C(100, 50) mod p = 538992043

Remember

Reduce after each operation; use long.
Fast power: O(log e).
Inverse = a^(p − 2) for prime p.

Common mistakes

Multiplying two reduced values in int (overflow).
Dividing directly under a modulus.

Command Palette

Modular Arithmetic, Fast Power and nCr

1.The rules