LeetCode 372 - Super Pow

The problem asks us to compute: The complication is that the exponent b is extremely large. Instead of being given as a normal integer, it is provided as an array of digits.

leetcodemediummathdivide-and-conquer

LeetCode Problem 372

Difficulty: 🟡 Medium
Topics: Math, Divide and Conquer

Solution

Problem Understanding

The problem asks us to compute:

$a^b \bmod 1337$

The complication is that the exponent b is extremely large. Instead of being given as a normal integer, it is provided as an array of digits. For example, if:

b = [1, 0, 2, 4]

then the exponent actually represents the number:

1024

The goal is to compute the modular exponentiation result efficiently without ever constructing the gigantic integer explicitly.

The modulus is fixed at 1337, which is relatively small. This is important because modular arithmetic allows us to keep intermediate numbers bounded and avoid overflow or huge computations.

A naive implementation might try to reconstruct the exponent and then compute:

a^b

directly. However, the exponent may contain up to 2000 digits, which means it can be astronomically large. Even storing that integer in standard numeric types is impossible.

The constraints reveal several important observations:

  • a can be as large as 2^31 - 1, so repeated multiplication without modular reduction would overflow in many languages.
  • b.length <= 2000, meaning the exponent can contain thousands of decimal digits.
  • Since the modulus is only 1337, modular exponentiation techniques become very effective.
  • The exponent digits are guaranteed to have no leading zeros, so the array always represents a valid positive integer.

Several edge cases are important:

  • a = 1, because any power of 1 remains 1.
  • Very large exponents, where constructing the number directly is impossible.
  • Digits containing zeros, such as [1,0], which represents 10 rather than separate operations.
  • Large values of a, which require modular reduction early and often.

Approaches

Brute Force Approach

The brute force idea is straightforward. First, reconstruct the integer represented by the digit array b. Then compute:

(a^b) % 1337

using repeated multiplication or a standard power function.

This approach is correct because it directly evaluates the mathematical definition of the problem.

However, it immediately becomes impractical because the exponent can have up to 2000 digits. A 2000 digit number is vastly larger than what built in integer types can store efficiently. Even languages with arbitrary precision integers would struggle to compute such an enormous exponent directly.

Additionally, repeated multiplication would require an impossible number of operations.

Optimal Approach

The key insight is that modular arithmetic allows exponent decomposition.

Suppose the exponent digits are processed left to right. If we already computed:

a^x mod 1337

and we append another digit d, the new exponent becomes:

10x + d

Using exponent rules:

$a^{10x+d} = (a^x)^{10} \cdot a^d$

Taking modulo 1337 throughout gives:

$a^{10x+d} \bmod 1337 = \left((a^x)^{10} \bmod 1337\right) \cdot \left(a^d \bmod 1337\right) \bmod 1337$

This means we never need the full exponent. We only maintain the current modular result while processing digits one by one.

Efficient modular exponentiation, often called binary exponentiation or fast power, lets us compute powers in logarithmic time.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential / infeasible Extremely large Attempts to build and use the full exponent
Optimal O(n log 10) O(1) Processes exponent digits incrementally using modular arithmetic

Here, n is the number of digits in b.

Algorithm Walkthrough

  1. Initialize the modulus as 1337.

Since every computation is performed modulo 1337, we store this constant once and reuse it throughout the algorithm. 2. Reduce a modulo 1337.

This prevents unnecessary large intermediate values because:

$(a \bmod m)^k \bmod m = a^k \bmod m$ 3. Initialize the running answer as 1.

This represents the value of:

a^0 mod 1337

before any exponent digits are processed. 4. Process each digit in b from left to right.

Suppose the current answer represents:

a^x mod 1337

and the next digit is d.

The new exponent becomes:

10x + d
  1. Raise the current answer to the 10th power modulo 1337.

This corresponds to:

(a^x)^10

We compute this efficiently using fast modular exponentiation. 6. Compute a^d mod 1337.

Since d is only a single decimal digit between 0 and 9, this computation is very small. 7. Multiply the two modular components together.

This produces:

a^(10x+d) mod 1337

which becomes the updated running answer. 8. Continue until all digits are processed.

After the final digit, the running answer equals:

a^b mod 1337

Why it works

The algorithm relies on the invariant that after processing the first i digits of b, the variable result equals:

a^(value represented by first i digits) mod 1337

Each new digit transforms exponent x into 10x + d. Using exponent laws and modular arithmetic, we correctly update the result without ever constructing the enormous exponent explicitly.

Python Solution

from typing import List

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337

        def mod_pow(base: int, exponent: int) -> int:
            result = 1
            base %= MOD

            while exponent > 0:
                if exponent % 2 == 1:
                    result = (result * base) % MOD

                base = (base * base) % MOD
                exponent //= 2

            return result

        result = 1
        a %= MOD

        for digit in b:
            result = (
                mod_pow(result, 10) * mod_pow(a, digit)
            ) % MOD

        return result

The implementation begins with a helper function mod_pow, which performs fast modular exponentiation using binary exponentiation. Instead of multiplying the base repeatedly, the exponent is halved at every iteration, reducing the complexity from linear to logarithmic.

Inside mod_pow, whenever the current exponent bit is odd, the current base contributes to the final answer. The base is squared after each step because binary exponentiation decomposes powers into powers of two.

The main function initializes result to 1, representing an empty exponent. The value of a is immediately reduced modulo 1337 to keep all future computations small.

For every digit in the exponent array, the algorithm updates the current result using the mathematical identity:

$a^{10x+d} = (a^x)^{10} \cdot a^d$

The expression:

mod_pow(result, 10)

handles the multiplication of the previous exponent by 10, while:

mod_pow(a, digit)

adds the new digit contribution.

The final result is returned after all digits are processed.

Go Solution

func superPow(a int, b []int) int {
	const MOD = 1337

	modPow := func(base int, exponent int) int {
		result := 1
		base %= MOD

		for exponent > 0 {
			if exponent%2 == 1 {
				result = (result * base) % MOD
			}

			base = (base * base) % MOD
			exponent /= 2
		}

		return result
	}

	result := 1
	a %= MOD

	for _, digit := range b {
		result = (modPow(result, 10) * modPow(a, digit)) % MOD
	}

	return result
}

The Go implementation mirrors the Python logic closely. Since Go does not support nested named functions as conveniently as Python, the helper is implemented as an inline closure assigned to modPow.

Go integers are sufficient here because all intermediate values remain bounded by the modulus 1337. After every multiplication, the modulo operation prevents overflow growth.

The exponent digits are processed using Go's range syntax over the slice.

Worked Examples

Example 1

Input: a = 2, b = [3]

The exponent is simply 3.

Step Digit Current Result Before Update Formula Result After
Start - 1 Initial value 1
1 3 1 (1^10 * 2^3) mod 1337 8

Final answer:

8

Example 2

Input: a = 2, b = [1,0]

The exponent is 10.

Step Digit Current Result Before Computation Result After
Start - 1 Initial value 1
1 1 1 (1^10 * 2^1) mod 1337 2
2 0 2 (2^10 * 2^0) mod 1337 1024

Final answer:

1024

Example 3

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

Since any power of 1 remains 1, every step stays unchanged.

Step Digit Current Result Before Result After
Start - 1 1
1 4 1 1
2 3 1 1
3 3 1 1
4 8 1 1
5 5 1 1
6 2 1 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log 10) Each digit requires two fast exponentiation operations with small exponents
Space O(1) Only a few integer variables are used

The exponentiation operations are extremely cheap because the exponents are at most 10 and 9. Therefore, each digit contributes only constant work. Since there are n digits, the overall runtime is linear in the size of the exponent array.

The algorithm uses constant extra memory because no additional data structures proportional to input size are allocated.

Test Cases

from typing import List

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337

        def mod_pow(base: int, exponent: int) -> int:
            result = 1
            base %= MOD

            while exponent > 0:
                if exponent % 2 == 1:
                    result = (result * base) % MOD

                base = (base * base) % MOD
                exponent //= 2

            return result

        result = 1
        a %= MOD

        for digit in b:
            result = (
                mod_pow(result, 10) * mod_pow(a, digit)
            ) % MOD

        return result

sol = Solution()

assert sol.superPow(2, [3]) == 8  # Basic small exponent
assert sol.superPow(2, [1, 0]) == 1024  # Multi-digit exponent
assert sol.superPow(1, [4, 3, 3, 8, 5, 2]) == 1  # Base equals 1
assert sol.superPow(2147483647, [2]) == pow(2147483647, 2, 1337)  # Large base
assert sol.superPow(2, [0]) == 1  # Zero exponent
assert sol.superPow(1337, [1]) == 0  # Base divisible by modulus
assert sol.superPow(1338, [1]) == 1  # Base just above modulus
assert sol.superPow(5, [9, 9, 9]) == pow(5, 999, 1337)  # Large exponent
assert sol.superPow(7, [1, 0, 0, 0]) == pow(7, 1000, 1337)  # Power with many zeros
assert sol.superPow(2, [2, 0, 0, 0]) == pow(2, 2000, 1337)  # Very large exponent
Test Why
a=2, b=[3] Verifies simplest normal case
a=2, b=[1,0] Verifies multi-digit exponent handling
a=1, b=[4,3,3,8,5,2] Ensures powers of 1 remain correct
a=2147483647, b=[2] Tests maximum base constraint
a=2, b=[0] Validates zero exponent behavior
a=1337, b=[1] Tests modulus reduction to zero
a=1338, b=[1] Ensures modulo reduction works properly
a=5, b=[9,9,9] Tests very large exponent values
a=7, b=[1,0,0,0] Verifies repeated exponent scaling
a=2, b=[2,0,0,0] Stress test with large exponent

Edge Cases

One important edge case occurs when the exponent is zero, such as b = [0]. Mathematically:

$a^0 = 1$

A buggy implementation might mishandle this because no multiplication steps contribute to the result. In this solution, result starts at 1, so processing digit 0 naturally preserves the correct value.

Another critical case is when a is divisible by 1337. For example:

a = 1337

After modular reduction:

a % 1337 = 0

Any positive exponent should therefore produce 0. Since the implementation immediately reduces a modulo 1337, this behavior emerges automatically.

A third important edge case is extremely large exponents with thousands of digits. Constructing the exponent explicitly would overflow memory or integer limits in many languages. The implementation avoids this entirely by processing digits incrementally and updating the modular result using exponent decomposition.

Finally, very large base values near 2^31 - 1 could cause overflow if intermediate values grew unchecked. The repeated modulo operations ensure every multiplication remains bounded, keeping computations safe and efficient.