Super Pow: Modular Exponentiation on Big Exponents

LeetCode Super Pow (Problem 372) gives you an integer a and an array b where the digits of b represent a very large exponent. If b = [1, 0, 4], the exponent is 104. Your job is to compute a^b mod 1337.

The exponent can have up to 2000 digits, so you cannot convert b to a regular integer first. A 2000-digit number is astronomically large. You need a smarter approach that processes the exponent one digit at a time and keeps intermediate results small.

Key insight: digit decomposition

The trick is to peel the exponent one digit at a time using this identity. If b = [d1, d2, ..., dk], then:

a^[d1, d2, ..., dk] = (a^[d1, ..., d(k-1)])^10 * a^dk

Think about why this works. The last digit contributes a^dk directly. Everything before it represents an exponent that is 10 times smaller, which you then raise to the 10th power to shift it back into position. You can verify this with a simple example: a^104 = (a^10)^10 * a^4.

Pair this with the modular arithmetic identity (a * b) mod m = ((a mod m) * (b mod m)) mod m, and every intermediate value stays below 1337. You never need to store a large number.

The approach: recursive decomposition

The recursive structure follows directly from the identity above.

Base case: an empty array means the exponent is zero, so a^0 = 1.

Recursive case: peel the last digit, recurse on the rest, then combine:

last = b.pop()
return pow(superPow(a, b), 10, 1337) * pow(a, last, 1337) % 1337

Python's built-in pow(base, exp, mod) computes modular exponentiation efficiently using fast exponentiation internally. You should use the three-argument form rather than (base ** exp) % mod, which would compute the full large value first.

Python solution

def superPow(a: int, b: list[int]) -> int:
    MOD = 1337
    if not b:
        return 1
    last = b.pop()
    return pow(superPow(a, b), 10, MOD) * pow(a, last, MOD) % MOD

Iterative version

The recursive solution works, but it mutates b and uses call stack space proportional to the number of digits. You can process the digits left to right with a simple loop:

def superPow(a: int, b: list[int]) -> int:
    MOD = 1337
    result = 1
    for digit in b:
        result = pow(result, 10, MOD) * pow(a, digit, MOD) % MOD
    return result

At each step, you raise the accumulated result to the 10th power (which shifts the exponent you have built up one decimal place to the left) and then multiply by a^digit (which adds the new digit's contribution). After processing all digits left to right, result holds a^b mod 1337.

This version is O(1) space and does not touch b at all.

Step-by-step trace

Complexity

Each call to pow(x, y, mod) uses fast exponentiation, running in O(log y) multiplications. You call it twice per digit with exponents 10 and at most 9, both small constants, so the per-digit cost simplifies to O(log a). Over all k digits the total is O(k log a).

Building blocks

Three ideas combine here.

Modular arithmetic identity. (a * b) mod m = ((a mod m) * (b mod m)) mod m. This is what lets you take mod at every intermediate step without changing the final result. Without it you would have to carry large numbers all the way through.

Fast exponentiation. Python's pow(x, y, mod) reduces y multiplications to O(log y) by squaring repeatedly. This is the same technique as Pow(x, n).

Digit-by-digit decomposition for large numbers. When a number is too large to fit in memory as an integer, you process it one digit at a time. The identity a^[d1..dk] = (a^[d1..d(k-1)])^10 * a^dk is the mathematical form of this idea applied to exponents.

Edge cases

a is a multiple of 1337: a mod 1337 = 0, so every pow(a, digit, 1337) = 0 for digit >= 1. The result is 0.

b = [0]: The exponent is zero. a^0 = 1 regardless of a. The loop runs once: result = pow(1, 10, 1337) * pow(a, 0, 1337) % 1337 = 1 * 1 = 1.

Single digit exponent: One iteration of the loop. result = pow(1, 10, 1337) * pow(a, digit, 1337) % 1337 = pow(a, digit, 1337).

a larger than 1337: pow(a, digit, mod) handles this correctly. Python's three-argument pow reduces the base modulo m before computing, so a large a is never a problem.

From understanding to recall

The core identity to memorize is a^[d1..dk] = (a^[d1..d(k-1)])^10 * a^dk. Once that lands, the loop writes itself: accumulate the result left to right, shift by raising to the 10th power, then fold in the current digit. The Python pow(x, y, mod) three-argument trick is the other thing to keep ready. Those two pieces are enough to reconstruct the solution from scratch.

Related posts

• Pow(x, n) - fast exponentiation by squaring, the underlying primitive that pow(x, y, mod) uses internally
• Power of Two - a simpler power-checking problem that shows why the base matters
• Power of Three - another modular arithmetic pattern with a neat divisibility shortcut