LeetCode 372: Super Pow

Problem Restatement

We are given:

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. (leetcode.com)

Input and Output

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)

4. Compute:

part1^10 mod MOD

5. Compute:

a^d mod MOD

6. Multiply both modulo MOD.

Use fast modular exponentiation for powers.

Correctness

Suppose the exponent represented by b is:

E = 10Q + d

where:

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:

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:

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:

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: