LeetCode 372: Super Pow

A clear explanation of computing large modular exponentiation using fast power, modular arithmetic, and digit decomposition.

leetcodemathmodular-arithmeticrecursionfast-power

Problem Restatement

We are given:

Variable Meaning
a Positive integer base
b Very large exponent represented as an array of digits

We need to compute:

a^b mod 1337

The exponent can be extremely large, so we cannot convert the entire digit array into a normal integer directly.

The problem statement defines:

b = [1, 2, 3]

as the exponent:

123

The modulus is always:

1337

The official examples include:

a = 2
b = [3]

with answer:

8

and:

a = 2
b = [1, 0]

with answer:

1024

modulo 1337.

Input and Output

Item Meaning
Input Integer a and digit array b
Output a^b mod 1337
Exponent format Decimal digits in array form
Modulus Always 1337

Example function shape:

def superPow(a: int, b: list[int]) -> int:
    ...

Examples

Example 1:

a = 2
b = [3]

This means:

2^3 = 8

Then:

8 mod 1337 = 8

So the answer is:

8

Example 2:

a = 2
b = [1, 0]

This means:

2^10 = 1024

Then:

1024 mod 1337 = 1024

So the answer is:

1024

Example 3:

a = 1
b = [4, 3, 3, 8, 5, 2]

Since:

1^anything = 1

the answer is:

1

First Thought: Build the Exponent

A direct idea is:

  1. Convert the digit array into a large integer.
  2. Compute:
pow(a, exponent, 1337)

Example:

b = [1, 2, 3]

becomes:

123

This works in Python because Python integers are arbitrary precision.

But the problem is designed to test modular exponentiation ideas rather than relying on huge integers.

We should solve it using exponent decomposition.

Key Insight

Suppose the exponent digits are:

b = [1, 2, 3]

Then:

123 = 12 * 10 + 3

So:

a^123 = a^(12 * 10 + 3)

Using exponent rules:

a^(x + y) = a^x * a^y

and:

a^(10x) = (a^x)^10

we get:

a^123 = (a^12)^10 * a^3

This creates a recursive structure.

If we remove the last digit d from the exponent:

remaining = previous digits

then:

a^(remaining * 10 + d)
=
(a^remaining)^10 * a^d

All computations are done modulo 1337.

Modular Arithmetic Rule

We repeatedly use:

(x * y) mod m
=
((x mod m) * (y mod m)) mod m

This keeps numbers small.

Algorithm

Define:

MOD = 1337

Recursive process:

  1. If b is empty:
    • Return 1.
  2. Remove the last digit d.
  3. Recursively compute:
part1 = superPow(a, remaining_digits)
  1. Compute:
part1^10 mod MOD
  1. Compute:
a^d mod MOD
  1. Multiply both modulo MOD.

Use fast modular exponentiation for powers.

Correctness

Suppose the exponent represented by b is:

E = 10Q + d

where:

Variable Meaning
Q Exponent formed by all digits except the last
d Last digit

Then:

a^E
=
a^(10Q + d)
=
(a^Q)^10 * a^d

The recursive call computes:

a^Q mod 1337

Raising it to the 10th power and multiplying by:

a^d mod 1337

produces:

a^E mod 1337

because modular multiplication preserves correctness.

The recursion eventually reaches the empty exponent, which represents exponent 0. Since:

a^0 = 1

the base case is correct.

Therefore, the algorithm correctly computes:

a^b mod 1337

for every valid input.

Complexity

Let:

Symbol Meaning
n Number of digits in b

Each recursion level processes one digit.

Fast exponentiation uses logarithmic time in the exponent.

But the only exponents used are:

10

and:

0 through 9

which are constant-size.

So:

Metric Value
Time O(n)
Space O(n) recursion stack

Implementation

class Solution:
    MOD = 1337

    def superPow(self, a: int, b: list[int]) -> int:
        if not b:
            return 1

        last_digit = b.pop()

        part1 = self._mod_pow(
            self.superPow(a, b),
            10,
        )

        part2 = self._mod_pow(a, last_digit)

        return (part1 * part2) % self.MOD

    def _mod_pow(self, base: int, exponent: int) -> int:
        result = 1
        base %= self.MOD

        while exponent > 0:
            if exponent & 1:
                result = (result * base) % self.MOD

            base = (base * base) % self.MOD
            exponent >>= 1

        return result

Code Explanation

The modulus is fixed:

MOD = 1337

The base case handles exponent 0:

if not b:
    return 1

We remove the last exponent digit:

last_digit = b.pop()

Suppose:

b = [1, 2, 3]

Then:

Part Meaning
Remaining digits 12
Last digit 3

The recursive call computes:

a^12 mod 1337

Then:

part1 = (a^12)^10 mod 1337

and:

part2 = a^3 mod 1337

Finally:

(part1 * part2) % MOD

gives:

a^123 mod 1337

The helper _mod_pow uses fast exponentiation.

Instead of multiplying base repeatedly, it squares the base and halves the exponent:

base = (base * base) % MOD
exponent >>= 1

This gives logarithmic exponentiation time.

Testing

def run_tests():
    s = Solution()

    assert s.superPow(2, [3]) == 8

    assert s.superPow(2, [1, 0]) == 1024

    assert s.superPow(1, [4, 3, 3, 8, 5, 2]) == 1

    assert s.superPow(2, [1, 2, 3]) == pow(2, 123, 1337)

    assert s.superPow(2147483647, [2, 0, 0]) == pow(2147483647, 200, 1337)

    print("all tests passed")

run_tests()

Test meaning:

Test Why
2^[3] Small exponent
2^[1,0] Multi-digit exponent
1^anything Multiplicative identity
2^[1,2,3] Recursive exponent decomposition
Large base Confirms modular reduction works