GCD & Modular Arithmetic

Fast Exponentiation

Computing a^n by multiplying n times is O(n). Instead square the base and halve the exponent: a^n is (a^(n/2))^2 for even n, and a * a^(n-1) for odd. That is O(log n), which turns 2^1000000007 from impossible into about 30 multiplications.

O(log n)

O(1)

say this out loud

The exponent is huge, so I square the base and halve the exponent instead of looping. That is O(log n), and the accumulator has to be a long.

How It Works

Binary exponentiation exploits the fact that a^n can be built from a^(n/2). If n is even, a^n is (a^(n/2)) squared. If n is odd, peel one factor off and recurse on n-1. Each step halves the exponent, so the total number of multiplications is O(log n) rather than n.

The iterative form is cleaner and is what to write in an interview: walk the bits of the exponent, keep squaring the base each step, and fold the base into the result only when the current bit is 1. That is exactly the binary expansion of the exponent, which is why 3^13 takes four multiplications instead of thirteen. Two practical details: apply the modulus after every multiply so nothing grows without bound, and use long for the running values because two ints near the modulus overflow int as soon as they are multiplied together.

Step-by-Step Visualization

Compute 3^13 by squaring. 13 is 1101 in binary

result1

exp1101

1/5

Code

Java

static long modPow(long base, long exp, long mod) {
  long result = 1;
  base %= mod;

  while (exp > 0) {
    if ((exp & 1) == 1)               // odd bit: fold base in
      result = result * base % mod;
    base = base * base % mod;         // square
    exp >>= 1;                        // halve
  }
  return result;
}

Tips & Gotchas

1Square the base and halve the exponent. Multiply into the answer only on odd bits

2Use long for the running product or a * a overflows int before the modulus is applied

3Negative exponents in Pow(x, n) need 1/x and careful handling of Integer.MIN_VALUE

Practice Problems

1Pow(x, n)
2Super Pow
3Count Good Numbers
4Number of Ways to Stay in the Same Place After Some Steps

About the GCD & Modular Arithmetic Pattern

Modular arithmetic is what lets you answer questions about enormous numbers without ever holding one. Addition and multiplication pass through the modulus cleanly, division does not, and the Euclidean algorithm underpins the whole area.

Key insight

Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.

Common Math & Number Theory Interview Problems

Count Primes
Pow(x, n)
Greatest Common Divisor of Strings
Excel Sheet Column Title
Ugly Number II
Factorial Trailing Zeroes

Frequently Asked Questions

Why must the running values be long?

With a modulus near 10^9, two residues multiply to nearly 10^18. That overflows a 32-bit int immediately but sits inside a 64-bit long, which tops out around 9.2 x 10^18. Declaring the accumulator and base as long is the entire fix, and forgetting it produces wrong answers rather than errors.

How do I handle a negative exponent in Pow(x, n)?

Compute the positive power and take the reciprocal. The trap is Integer.MIN_VALUE, whose negation overflows, so widen n to a long before negating it. That single cast is what the problem is really testing.

Does this work for matrix exponentiation too?

Yes, and that is where it earns the most. Replace scalar multiplication with matrix multiplication and the same halving computes the nth Fibonacci number in O(log n), or counts paths of length n in a graph. The algorithm only needs an associative operation.