Loading…

mediumMath GeometryFrequently asked

Modular Exponentiation

Q: How do you solve Modular Exponentiation using the Iterative Multiply exp Times (Baseline) approach?

When to use it: State it first to expose the two problems you're about to fix: O(exp) time and unbounded growth. The literal definition says base^exp is base times itself exp times. So keep a running `result = 1` and multiply by base on each of exp iterations, reducing mod m every step to keep the number small. **Why the mod-every-step part is already right.** Reducing after each multiply uses the core identity (a·b) mod m = ((a mod m)·(b mod m)) mod m. This keeps `result` below m at all times, so it never overflows regardless of how large exp is. That half of the idea carries straight over to the fast version. **Why this still fails the problem.** The loop runs exp times. The constraints allow exp up to 10¹⁸; even at a billion multiplications per second that's over 30 years. An O(exp) algorithm simply cannot finish. The modular reduction fixed the *size* of the numbers but not the *number of operations*. **What we actually need.** We want the same correct, bounded multiplications, but far fewer of them. The insight is that base^exp can be assembled from a handful of repeated squarings rather than exp individual multiplies — which is exactly what binary exponentiation does, cutting the count to log₂(exp). Time complexity: O(exp). Space complexity: O(1).

Math & Number Theory · 15 of 36 · 10 min

Given non-negative integers base, exp, and a positive integer m, compute (base^exp) mod m.

exp can be very large (up to 10¹⁸), so you cannot compute base^exp and then take the modulus — the intermediate value would have billions of digits. You must combine the exponentiation with the modular reduction.

This is the engine behind LeetCode 50 (Pow(x, n), the non-modular real-number twin) and LeetCode 372 (Super Pow).

In plain English

We want base raised to a possibly enormous power, but only its remainder mod m. Two facts make it tractable: modular arithmetic lets us reduce after every multiplication ((a·b) mod m = ((a mod m)·(b mod m)) mod m), and the exponent can be consumed in binary so we do log₂(exp) multiplications instead of exp of them.

Examples

Example 1

Input: base = 2, exp = 10, m = 1000
Output: 24
Note: 2^10 = 1024, and 1024 mod 1000 = 24.

Example 2

Input: base = 3, exp = 0, m = 7
Output: 1
Note: Any base to the 0 power is 1; 1 mod 7 = 1.

Example 3

Input: base = 7, exp = 256, m = 13
Output: 9
Note: Binary exponentiation squares 7 mod 13 eight times (256 = 2^8) and reduces each step, landing on 9.

Constraints

0 ≤ base ≤ 10⁹
0 ≤ exp ≤ 10¹⁸
1 ≤ m ≤ 10⁹ (so operands fit and long products stay below 2⁶³)
Return a value in [0, m−1]

Clarifying questions4First question: How large can exp be?Explore questions

Q1.How large can exp be?
Up to 10¹⁸, which is why an O(exp) loop is hopeless — we need O(log exp) via binary exponentiation.
Q2.Is m guaranteed prime?
Not for the core problem. If it is prime, I can also compute modular inverses via Fermat's little theorem (a^(m−2) mod m), but the exponentiation itself doesn't require it.
Q3.What should base^0 return, especially when m = 1?
1 mod m. For m = 1 that's 0, since everything is congruent to 0 mod 1. I return `1 % m` to cover it.
Q4.How big can m be — does the product of two reduced operands overflow?
If m ≤ ~3×10⁹, two operands below m multiply to under 9×10¹⁸ < 2⁶³, safe in a Java long. Above that I'd use 128-bit multiplication or BigInteger.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

To compute base^exp mod m without the number exploding, never build base^exp first. Use fast (binary) exponentiation: square the base each step and multiply it into the answer only on the set bits of exp, taking `mod m` after every multiplication. That turns exp multiplications into about log₂(exp). Critical overflow note: in Java, multiplying two numbers each up to m−1 (≈10⁹) overflows a 32-bit int and even a long if m is near 2⁶³, so reduce mod m every step and use long (or 128-bit / BigInteger) when m is large.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you avoid computing base^exp directly (which overflows and is O(exp)), reach for binary exponentiation, and reduce mod m at every step to keep operands bounded.

Where candidates slip

Looping exp times (O(exp) — too slow for exp = 10⁹), or multiplying without taking mod each step so the product overflows long.

How to stand out

Explain WHY squaring halves the exponent (each bit of exp doubles the accounted-for power), prove correctness by the binary expansion of exp, and call out the exact overflow boundary in Java (long products must stay below 2⁶³).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative Multiply exp Times (Baseline)	`O(exp)`	`O(1)`	State it first to expose the two problems you're about to fix: O(exp) time and unbounded growth.	Read
2	Binary (Fast) Exponentiation (Optimal)Optimal	`O(log exp)`	`O(1)`	The answer they want. Pitch it as 'square the base, multiply on set bits of exp' and reduce mod m every step.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewresult = 1 base %= mexp > 0 ?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Iterative Multiply exp Times (Baseline)

TimeO(exp)SpaceO(1)

State it first to expose the two problems you're about to fix: O(exp) time and unbounded growth.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition of base^exp is base multiplied by itself exp times. What's the most direct loop for that?

2Hint 2Explore hint

Multiply a running product by base, exp times. To control growth, take the result mod m after each multiplication.

3Hint 3Explore hint

Now look at the loop count: if exp is 10¹⁸, this loop runs 10¹⁸ times — far too slow. That's the cost you need to cut.

A · Core idea

The literal definition says base^exp is base times itself exp times. So keep a running result = 1 and multiply by base on each of exp iterations, reducing mod m every step to keep the number small.

Why the mod-every-step part is already right. Reducing after each multiply uses the core identity (a·b) mod m = ((a mod m)·(b mod m)) mod m. This keeps result below m at all times, so it never overflows regardless of how large exp is. That half of the idea carries straight over to the fast version.

Why this still fails the problem. The loop runs exp times. The constraints allow exp up to 10¹⁸; even at a billion multiplications per second that's over 30 years. An O(exp) algorithm simply cannot finish. The modular reduction fixed the size of the numbers but not the number of operations.

What we actually need. We want the same correct, bounded multiplications, but far fewer of them. The insight is that base^exp can be assembled from a handful of repeated squarings rather than exp individual multiplies — which is exactly what binary exponentiation does, cutting the count to log₂(exp).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

base = 2, exp = 5, m = 1000

i=1

result = 1*2 = 2

State2

Final result32

C · Code with teaching comments

Reference implementation previewpublic long modPow(long base, long exp, long m) { long result = 1 % m; base %= m; for (long i = 0; i < exp; i++) { result = (result * base) % m;Explore the full code

solution.javaJava

Iterative Multiply exp Times (Baseline) — reference

2 teaching notes

1
public long modPow(long base, long exp, long m) {
2
    // 1 % m handles m = 1 (answer 0) and base^0 cleanly.
3
    long result = 1 % m;
4
    base %= m;
5
    for (long i = 0; i < exp; i++) {
6
        // Reduce every step so result stays below m and never overflows — but this runs
7
        // exp times.
8
        result = (result * base) % m;
9
    }
10
    return result;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(exp) timeO(1) spaceOpen the invariant and proofExplore the proof

The baseline already nails the numeric problem — reduce mod m every multiply and nothing overflows. Its only flaw is the count of multiplications. Recognising that 'O(exp) is the bottleneck, not overflow' points directly at logarithmic exponentiation as the fix.

ComplexityO(exp) time, O(1) space — The loop body runs exp times, each doing one constant-time modular multiply, so O(exp). Only a couple of scalars are kept, so O(1) space.

E · Edge cases and pitfalls3Using this when exp is large — O(exp) is far too slow.Explore edge cases

Pitfalls

Using this when exp is large — O(exp) is far too slow.
Building base^exp first and then taking mod — the intermediate has billions of digits and overflows.
Forgetting result = 1 % m so m = 1 wrongly returns 1 instead of 0.

03.2

Approach 2 of 2 · Optimal

Binary (Fast) Exponentiation (Optimal)

TimeO(log exp)SpaceO(1)

The answer they want. Pitch it as 'square the base, multiply on set bits of exp' and reduce mod m every step.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

base^exp where exp is huge: can you express base^exp using base^(exp/2)? Note base^exp = (base^(exp/2))² when exp is even.

2Hint 2Explore hint

Write exp in binary. base^13 = base^8 · base^4 · base^1, because 13 = 1101₂. So you only need the squared powers base^(2^k) and a way to pick which ones to multiply in.

3Hint 3Explore hint

Iterate: keep squaring base to get base^1, base^2, base^4, base^8, …; whenever the current low bit of exp is 1, multiply that squared power into the result. Reduce mod m after every multiply.

A · Core idea

Write the exponent in binary. If exp = b_k…b_1 b_0 in binary, then exp = Σ b_i · 2^i over the set bits, and therefore base^exp = ∏ base^(2^i) over the i where b_i = 1. We never need base^exp itself — only the squared powers base^(2^0), base^(2^1), … and a rule for which to combine.

The square-and-multiply mechanic. Maintain result = 1 and a running b that starts at base. Each iteration: if the lowest bit of exp is 1, fold the current b into the result; then square b (so it advances from base^(2^i) to base^(2^(i+1))); then shift exp right by one bit. After log₂(exp) iterations every bit has been consumed and result holds the product of exactly the squared powers selected by the set bits.

Why this is correct — the binary expansion. Because exp = Σ_{b_i=1} 2^i, exponent laws give base^exp = base^(Σ 2^i) = ∏_{b_i=1} base^(2^i). The loop produces base^(2^i) in b at exactly iteration i (one squaring per step), and multiplies it into result precisely when bit i is set. So result ends as that exact product — no more, no less. The mod-every-step reduction is justified by (a·b) mod m = ((a mod m)(b mod m)) mod m, which lets us reduce freely without changing the final remainder.

Why it halves the exponent. Each iteration does exp >>= 1, literally dividing the remaining exponent by two (dropping the consumed bit). Starting from exp, you reach 0 after ⌊log₂ exp⌋ + 1 halvings — that's why exp = 10¹⁸ needs only about 60 iterations instead of 10¹⁸.

Overflow, precisely. Both result and b are kept below m by reducing after every multiply. The danger is the multiplication itself: result * b with both up to m−1 produces up to (m−1)² . For m ≤ ~3×10⁹ that product is below 9×10¹⁸ < 2⁶³, so a Java long holds it. If m can be larger (close to 2⁶³), even the long product overflows — then use Math.multiplyHigh / 128-bit multiplication, or BigInteger.modPow. Python integers are unbounded, so the language removes the overflow worry entirely (at some speed cost).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

base = 3, exp = 13, m = 1000 (13 = 1101₂)

Array state

bit 0 = 1

multiply b=3 in; result=3

[0]

[1]

[2]

bit ↓

[3]

Current pointerResolved stateNot processed

Final result323 (3^13 = 1594323, and 1594323 mod 1000 = 323)

C · Code with teaching comments

solution.javaJava

Binary (Fast) Exponentiation (Optimal) — optimal

6 teaching notes

1
public long modPow(long base, long exp, long m) {
2
    // Everything is 0 mod 1; short-circuit so the rest can assume m ≥ 2.
3
    if (m == 1) return 0;
4
    long result = 1;
5
    // Reduce once up front so the first square stays below m².
6
    base %= m;
7
    while (exp > 0) {
8
        // The lowest bit of exp decides whether the current squared power joins the
9
        // product.
10
        if ((exp & 1) == 1) {
11
            // Fold in base^(2^i). Both operands < m, so for m ≤ ~3e9 the long product
12
            // stays below 2⁶³.
13
            result = (result * base) % m;
14
        }
15
        // Square to advance base from base^(2^i) to base^(2^(i+1)); reduce to stay
16
        // bounded.
17
        base = (base * base) % m;
18
        // Drop the consumed bit — this is the halving that gives O(log exp).
19
        exp >>= 1;
20
    }
21
    return result;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(log exp) timeO(1) spaceOpen the invariant and proofExplore the proof

Fast exponentiation is doubling in disguise: squaring the base doubles the exponent it represents, so the binary digits of exp tell you exactly which doublings to keep. The identical 'combine on set bits, square each step' template works for any associative operation — multiply matrices instead of numbers and you get Fibonacci / linear recurrences in O(log n).

ComplexityO(log exp) time, O(1) space — Each iteration strips one bit of exp (exp >>= 1), so the loop runs ⌊log₂ exp⌋ + 1 times. Each iteration does at most two modular multiplications, both O(1). Hence O(log exp) time and O(1) space.

E · Edge cases and pitfalls7exp = 0 — while loop never runs; result stays 1 (or 0 when m = 1) → base^0 = 1.Explore edge cases

Edge cases handled

exp = 0while loop never runs; result stays 1 (or 0 when m = 1) → base^0 = 1.
base = 0, exp = 5, m = 7base %= m = 0; result becomes 0 on the first set bit → 0.
m = 1Early return 0 — every value is congruent to 0 mod 1.

Pitfalls

Not reducing base %= m before the loop — the first square can be needlessly large.
Forgetting the mod after squaring base — base grows and the next product overflows.
Assuming a Java long is always safe — (m−1)² overflows long when m is near 2⁶³; use 128-bit or BigInteger.
Using exp / 2 with a signed shift bug, or `exp >> 1` on a negative — exp is non-negative here, but guard if it could be.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long modPow(long base, long exp, long m) { if (m == 1) return 0; long result = 1; base %= m; while (exp > 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Building the full power before reducing

base^exp can have billions of digits; in Java it overflows long instantly, and even in Python it's astronomically slow. Reduce mod m at every multiplication instead.

Explore the code comparison

Don't write this

long power = 1;
for (long i = 0; i < exp; i++) power *= base;  // overflows
return power % m;

Write this instead

long result = 1;
base %= m;
while (exp > 0) {
    if ((exp & 1) == 1) result = (result * base) % m;
    base = (base * base) % m;
    exp >>= 1;
}
return result;

Forgetting to reduce after squaring

If base isn't reduced after base = base*base, it can exceed m and the next product (m'·m') blows past 2⁶³, overflowing the long silently.

Explore the code comparison

Don't write this

base = base * base;            // not reduced — grows unbounded
result = (result * base) % m;

Write this instead

base = (base * base) % m;      // reduced every step
result = (result * base) % m;

Ignoring overflow when m is large

Two operands below m multiply to nearly m². If m ≈ 2⁶³ that product overflows even a long. Use 128-bit multiplication or BigInteger when m can be that big.

Explore the code comparison

Don't write this

result = (result * base) % m;  // (m-1)^2 overflows long for huge m

Write this instead

result = BigInteger.valueOf(result)
        .multiply(BigInteger.valueOf(base))
        .mod(BigInteger.valueOf(m)).longValue();

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Square-and-multiply over the bits of the exponent

Code pattern to memorize

result = 1
base %= m
while exp > 0:
    if exp & 1: result = (result * base) % m
    base = (base * base) % m
    exp >>= 1
return result

Rules to remember

1Reduce base %= m before the loop and take % m after every multiply — keep all operands below m so products stay bounded.
2Halve the exponent each step (exp >>= 1) and square the base — the exponent shrinks from exp to ~log₂(exp) iterations.
3Multiply base into result only when the current bit is 1 (exp & 1). The bits of exp select which squared powers to combine.
4In Java, two longs up to ~10⁹ multiply safely (product < 10¹⁸ < 2⁶³), but if m can exceed ~3×10⁹ use Math.multiplyHigh, 128-bit, or BigInteger to avoid overflow.
5Handle exp = 0 → return 1 % m (not 1; if m = 1 the answer is 0), and reduce a possibly-zero or negative base correctly first.

Use this pattern when

Compute base^exp mod m where exp is huge (10⁹, 10¹⁸, or bigger)
Modular inverse via Fermat: a^(m−2) mod m for prime m
Hashing, RSA-style crypto, combinatorics with a fixed modulus (nCr mod p)
Any recurrence you can express as a matrix power → matrix fast exponentiation

Choose another pattern when

exp is tiny (≤ 30 or so) → a plain loop is fine and clearer
No modulus and the result fits in 64 bits → just compute it directly
You need the exact (non-modular) huge power → use BigInteger.pow, not modular reduction
m is not prime but you need an inverse → Fermat fails; use extended Euclid instead

Interview takeaway

Fast exponentiation is the 'logarithmic doubling' idea applied to multiplication: write exp in binary, and each bit either contributes the current squared power or skips it. Squaring doubles the exponent you've accounted for, so you reach exp in log₂(exp) steps. The same square-and-combine skeleton generalises to matrix powers for linear recurrences like Fibonacci in O(log n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Square-and-Multiply. Whenever you raise something to a large power under an associative operation — integers mod m, matrices, polynomials — express the exponent in binary and combine the repeated squarings. The skeleton is identical; only the 'multiply' changes.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Pow(x, n)
Coming soon
Same binary exponentiation on a real base; handle negative n by inverting and the INT_MIN edge.
Super Pow
Coming soon
Exponent given as a digit array; combine per-digit fast exponentiation with a fixed modulus.
Modular Inverse via Fermat
Coming soon
For prime m, a⁻¹ ≡ a^(m−2) mod m — one modular exponentiation.
Matrix Fast Exponentiation
Coming soon
Replace scalar multiply with matrix multiply to compute linear recurrences (Fibonacci) in O(log n).

Same pattern

←

GCD and LCM

Continue · Next problem

Sieve of Eratosthenes

mediumMath GeometryFrequently asked

Modular Exponentiation

Math & Number Theory · 15 of 36 · 10 min

Given non-negative integers base, exp, and a positive integer m, compute (base^exp) mod m.

This is the engine behind LeetCode 50 (Pow(x, n), the non-modular real-number twin) and LeetCode 372 (Super Pow).

In plain English

Examples

Example 1

Input: base = 2, exp = 10, m = 1000
Output: 24
Note: 2^10 = 1024, and 1024 mod 1000 = 24.

Example 2

Input: base = 3, exp = 0, m = 7
Output: 1
Note: Any base to the 0 power is 1; 1 mod 7 = 1.

Example 3

Input: base = 7, exp = 256, m = 13
Output: 9
Note: Binary exponentiation squares 7 mod 13 eight times (256 = 2^8) and reduces each step, landing on 9.

Constraints

0 ≤ base ≤ 10⁹
0 ≤ exp ≤ 10¹⁸
1 ≤ m ≤ 10⁹ (so operands fit and long products stay below 2⁶³)
Return a value in [0, m−1]

Clarifying questions4First question: How large can exp be?Explore questions

Q1.How large can exp be?
Up to 10¹⁸, which is why an O(exp) loop is hopeless — we need O(log exp) via binary exponentiation.
Q2.Is m guaranteed prime?
Not for the core problem. If it is prime, I can also compute modular inverses via Fermat's little theorem (a^(m−2) mod m), but the exponentiation itself doesn't require it.
Q3.What should base^0 return, especially when m = 1?
1 mod m. For m = 1 that's 0, since everything is congruent to 0 mod 1. I return `1 % m` to cover it.
Q4.How big can m be — does the product of two reduced operands overflow?
If m ≤ ~3×10⁹, two operands below m multiply to under 9×10¹⁸ < 2⁶³, safe in a Java long. Above that I'd use 128-bit multiplication or BigInteger.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you avoid computing base^exp directly (which overflows and is O(exp)), reach for binary exponentiation, and reduce mod m at every step to keep operands bounded.

Where candidates slip

Looping exp times (O(exp) — too slow for exp = 10⁹), or multiplying without taking mod each step so the product overflows long.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative Multiply exp Times (Baseline)	`O(exp)`	`O(1)`	State it first to expose the two problems you're about to fix: O(exp) time and unbounded growth.	Read
2	Binary (Fast) Exponentiation (Optimal)Optimal	`O(log exp)`	`O(1)`	The answer they want. Pitch it as 'square the base, multiply on set bits of exp' and reduce mod m every step.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Iterative Multiply exp Times (Baseline)

TimeO(exp)SpaceO(1)

State it first to expose the two problems you're about to fix: O(exp) time and unbounded growth.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition of base^exp is base multiplied by itself exp times. What's the most direct loop for that?

2Hint 2Explore hint

Multiply a running product by base, exp times. To control growth, take the result mod m after each multiplication.

3Hint 3Explore hint

Now look at the loop count: if exp is 10¹⁸, this loop runs 10¹⁸ times — far too slow. That's the cost you need to cut.

A · Core idea

The literal definition says base^exp is base times itself exp times. So keep a running result = 1 and multiply by base on each of exp iterations, reducing mod m every step to keep the number small.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

base = 2, exp = 5, m = 1000

i=1

result = 1*2 = 2

State2

Final result32

C · Code with teaching comments

Reference implementation previewpublic long modPow(long base, long exp, long m) { long result = 1 % m; base %= m; for (long i = 0; i < exp; i++) { result = (result * base) % m;Explore the full code

solution.javaJava

Iterative Multiply exp Times (Baseline) — reference

2 teaching notes

1
public long modPow(long base, long exp, long m) {
2
    // 1 % m handles m = 1 (answer 0) and base^0 cleanly.
3
    long result = 1 % m;
4
    base %= m;
5
    for (long i = 0; i < exp; i++) {
6
        // Reduce every step so result stays below m and never overflows — but this runs
7
        // exp times.
8
        result = (result * base) % m;
9
    }
10
    return result;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(exp) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(exp) time, O(1) space — The loop body runs exp times, each doing one constant-time modular multiply, so O(exp). Only a couple of scalars are kept, so O(1) space.

E · Edge cases and pitfalls3Using this when exp is large — O(exp) is far too slow.Explore edge cases

Pitfalls

Using this when exp is large — O(exp) is far too slow.
Building base^exp first and then taking mod — the intermediate has billions of digits and overflows.
Forgetting result = 1 % m so m = 1 wrongly returns 1 instead of 0.

03.2

Approach 2 of 2 · Optimal

Binary (Fast) Exponentiation (Optimal)

TimeO(log exp)SpaceO(1)

The answer they want. Pitch it as 'square the base, multiply on set bits of exp' and reduce mod m every step.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

base^exp where exp is huge: can you express base^exp using base^(exp/2)? Note base^exp = (base^(exp/2))² when exp is even.

2Hint 2Explore hint

Write exp in binary. base^13 = base^8 · base^4 · base^1, because 13 = 1101₂. So you only need the squared powers base^(2^k) and a way to pick which ones to multiply in.

3Hint 3Explore hint

Iterate: keep squaring base to get base^1, base^2, base^4, base^8, …; whenever the current low bit of exp is 1, multiply that squared power into the result. Reduce mod m after every multiply.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

base = 3, exp = 13, m = 1000 (13 = 1101₂)

Array state

bit 0 = 1

multiply b=3 in; result=3

[0]

[1]

[2]

bit ↓

[3]

Current pointerResolved stateNot processed

Final result323 (3^13 = 1594323, and 1594323 mod 1000 = 323)

C · Code with teaching comments

solution.javaJava

Binary (Fast) Exponentiation (Optimal) — optimal

6 teaching notes

1
public long modPow(long base, long exp, long m) {
2
    // Everything is 0 mod 1; short-circuit so the rest can assume m ≥ 2.
3
    if (m == 1) return 0;
4
    long result = 1;
5
    // Reduce once up front so the first square stays below m².
6
    base %= m;
7
    while (exp > 0) {
8
        // The lowest bit of exp decides whether the current squared power joins the
9
        // product.
10
        if ((exp & 1) == 1) {
11
            // Fold in base^(2^i). Both operands < m, so for m ≤ ~3e9 the long product
12
            // stays below 2⁶³.
13
            result = (result * base) % m;
14
        }
15
        // Square to advance base from base^(2^i) to base^(2^(i+1)); reduce to stay
16
        // bounded.
17
        base = (base * base) % m;
18
        // Drop the consumed bit — this is the halving that gives O(log exp).
19
        exp >>= 1;
20
    }
21
    return result;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(log exp) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7exp = 0 — while loop never runs; result stays 1 (or 0 when m = 1) → base^0 = 1.Explore edge cases

Edge cases handled

exp = 0while loop never runs; result stays 1 (or 0 when m = 1) → base^0 = 1.
base = 0, exp = 5, m = 7base %= m = 0; result becomes 0 on the first set bit → 0.
m = 1Early return 0 — every value is congruent to 0 mod 1.

Pitfalls

Not reducing base %= m before the loop — the first square can be needlessly large.
Forgetting the mod after squaring base — base grows and the next product overflows.
Assuming a Java long is always safe — (m−1)² overflows long when m is near 2⁶³; use 128-bit or BigInteger.
Using exp / 2 with a signed shift bug, or `exp >> 1` on a negative — exp is non-negative here, but guard if it could be.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long modPow(long base, long exp, long m) { if (m == 1) return 0; long result = 1; base %= m; while (exp > 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Building the full power before reducing

base^exp can have billions of digits; in Java it overflows long instantly, and even in Python it's astronomically slow. Reduce mod m at every multiplication instead.

Explore the code comparison

Don't write this

long power = 1;
for (long i = 0; i < exp; i++) power *= base;  // overflows
return power % m;

Write this instead

long result = 1;
base %= m;
while (exp > 0) {
    if ((exp & 1) == 1) result = (result * base) % m;
    base = (base * base) % m;
    exp >>= 1;
}
return result;

Forgetting to reduce after squaring

If base isn't reduced after base = base*base, it can exceed m and the next product (m'·m') blows past 2⁶³, overflowing the long silently.

Explore the code comparison

Don't write this

base = base * base;            // not reduced — grows unbounded
result = (result * base) % m;

Write this instead

base = (base * base) % m;      // reduced every step
result = (result * base) % m;

Ignoring overflow when m is large

Two operands below m multiply to nearly m². If m ≈ 2⁶³ that product overflows even a long. Use 128-bit multiplication or BigInteger when m can be that big.

Explore the code comparison

Don't write this

result = (result * base) % m;  // (m-1)^2 overflows long for huge m

Write this instead

result = BigInteger.valueOf(result)
        .multiply(BigInteger.valueOf(base))
        .mod(BigInteger.valueOf(m)).longValue();

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Square-and-multiply over the bits of the exponent

Code pattern to memorize

result = 1
base %= m
while exp > 0:
    if exp & 1: result = (result * base) % m
    base = (base * base) % m
    exp >>= 1
return result

Rules to remember

1Reduce base %= m before the loop and take % m after every multiply — keep all operands below m so products stay bounded.
2Halve the exponent each step (exp >>= 1) and square the base — the exponent shrinks from exp to ~log₂(exp) iterations.
3Multiply base into result only when the current bit is 1 (exp & 1). The bits of exp select which squared powers to combine.
4In Java, two longs up to ~10⁹ multiply safely (product < 10¹⁸ < 2⁶³), but if m can exceed ~3×10⁹ use Math.multiplyHigh, 128-bit, or BigInteger to avoid overflow.
5Handle exp = 0 → return 1 % m (not 1; if m = 1 the answer is 0), and reduce a possibly-zero or negative base correctly first.

Use this pattern when

Compute base^exp mod m where exp is huge (10⁹, 10¹⁸, or bigger)
Modular inverse via Fermat: a^(m−2) mod m for prime m
Hashing, RSA-style crypto, combinatorics with a fixed modulus (nCr mod p)
Any recurrence you can express as a matrix power → matrix fast exponentiation

Choose another pattern when

exp is tiny (≤ 30 or so) → a plain loop is fine and clearer
No modulus and the result fits in 64 bits → just compute it directly
You need the exact (non-modular) huge power → use BigInteger.pow, not modular reduction
m is not prime but you need an inverse → Fermat fails; use extended Euclid instead

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Pow(x, n)
Coming soon
Same binary exponentiation on a real base; handle negative n by inverting and the INT_MIN edge.
Super Pow
Coming soon
Exponent given as a digit array; combine per-digit fast exponentiation with a fixed modulus.
Modular Inverse via Fermat
Coming soon
For prime m, a⁻¹ ≡ a^(m−2) mod m — one modular exponentiation.
Matrix Fast Exponentiation
Coming soon
Replace scalar multiply with matrix multiply to compute linear recurrences (Fibonacci) in O(log n).

Same pattern

←

GCD and LCM

Continue · Next problem

Sieve of Eratosthenes