Problem Description

You need to calculate a^b mod 1337, where:

• a is a positive integer
• b is an extremely large positive integer represented as an array of digits

For example, if b = [1, 2, 3], this represents the number 123.

The challenge is that b can be so large that it cannot fit in any standard integer data type, which is why it's given as an array of digits. You need to find the remainder when a raised to this massive power is divided by 1337.

The solution uses the property that a^(10*x + y) = (a^10)^x * a^y. By processing the digits of b from right to left, we can break down the large exponentiation into manageable pieces:

• For each digit e in b (starting from the least significant), we multiply our result by a^e mod 1337
• After processing each digit, we update a to a^10 mod 1337 to account for the next digit position (which represents a power 10 times larger)

This approach avoids computing the actual value of a^b (which would be astronomically large) and instead maintains all intermediate results modulo 1337.

Intuition

When faced with computing a^b mod 1337 where b is extremely large, the key insight is to decompose the exponent using positional notation.

Consider how we write numbers: 123 = 1×10² + 2×10¹ + 3×10⁰. This means a^123 = a^(100+20+3) = a^100 × a^20 × a^3.

We can rewrite this as: a^123 = (a^100) × (a^20) × (a^3) = ((a^10)^10)^1 × (a^10)^2 × a^3.

This reveals a pattern: if we process the digits from right to left, we can build up the result incrementally:

1. Start with the rightmost digit: compute a^3
2. Move to the next digit (2): we need (a^10)^2, so update our base to a^10
3. Move to the next digit (1): we need ((a^10)^10)^1, so update our base again to (a^10)^10

The beauty of this approach is that at each step, we only need to:

• Compute a^digit where digit is between 0-9 (small exponent)
• Update our base by raising it to the 10th power for the next position

Since we're working with modular arithmetic, we can apply the mod operation at each step to keep numbers manageable. The property (x × y) mod m = ((x mod m) × (y mod m)) mod m ensures our intermediate results stay small while preserving correctness.

This transforms an impossible computation (raising a number to a power with hundreds of digits) into a series of simple operations with single-digit exponents.

Solution Approach

The implementation follows the mathematical decomposition we identified:

1. Initialize variables:

   • Set mod = 1337 as our modulus
   • Initialize ans = 1 to accumulate our result
   • We'll process the digits of b in reverse order

2. Process each digit from right to left:

   for e in b[::-1]:

   We reverse the array b to process digits from least significant to most significant.

3. For each digit position:

   • Multiply the answer by a^e mod 1337:

     ans = ans * pow(a, e, mod) % mod

     This handles the contribution of the current digit. Python's built-in pow(a, e, mod) efficiently computes a^e mod 1337.

   • Update the base for the next digit position:

     a = pow(a, 10, mod)

     Since the next digit represents a power that's 10 times larger in magnitude, we transform a to a^10 mod 1337. This becomes our new base for the next iteration.

4. Return the final result: After processing all digits, ans contains a^b mod 1337.

Example walkthrough with a = 2, b = [1, 0] (representing 10):

• First iteration (digit 0): ans = 1 * 2^0 % 1337 = 1, then a = 2^10 % 1337 = 1024
• Second iteration (digit 1): ans = 1 * 1024^1 % 1337 = 1024
• Result: 2^10 mod 1337 = 1024

The algorithm runs in O(n) time where n is the number of digits in b, with each iteration performing constant-time modular exponentiation operations with small exponents (at most 10).

Example Walkthrough

Let's trace through the algorithm with a = 3 and b = [2, 3, 4] (representing 234).

We want to calculate 3^234 mod 1337.

Initial Setup:

• mod = 1337
• ans = 1
• We'll process b in reverse: [4, 3, 2]

Iteration 1 (digit = 4, ones place):

• Calculate contribution: ans = 1 * pow(3, 4, 1337) = 1 * 81 = 81
• Update base for next position: a = pow(3, 10, 1337) = 59049 % 1337 = 168
• After iteration 1: ans = 81, a = 168

Iteration 2 (digit = 3, tens place):

• We need (3^10)^3 for the tens position
• Calculate contribution: ans = 81 * pow(168, 3, 1337) % 1337
  • pow(168, 3, 1337) = 4741632 % 1337 = 1118
  • ans = 81 * 1118 % 1337 = 90558 % 1337 = 966
• Update base for next position: a = pow(168, 10, 1337) = 1198
• After iteration 2: ans = 966, a = 1198

Iteration 3 (digit = 2, hundreds place):

• We need ((3^10)^10)^2 for the hundreds position
• Calculate contribution: ans = 966 * pow(1198, 2, 1337) % 1337
  • pow(1198, 2, 1337) = 1435204 % 1337 = 202
  • ans = 966 * 202 % 1337 = 195132 % 1337 = 1131

Final Result: 3^234 mod 1337 = 1131

The key insight is how we build up the answer position by position:

• Ones place: 3^4
• Tens place: (3^10)^3
• Hundreds place: ((3^10)^10)^2

Each iteration handles one digit while maintaining all calculations modulo 1337 to keep numbers manageable.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log m) where n is the length of array b and m = 1337 is the modulus.

• The main loop iterates through each digit in array b, which takes O(n) iterations
• Inside each iteration:
  • pow(a, e, mod) performs modular exponentiation with exponent e (where 0 ≤ e ≤ 9), taking O(log e) = O(1) time since e is at most 9
  • pow(a, 10, mod) performs modular exponentiation with exponent 10, taking O(log 10) = O(1) time
  • The modulo operation % mod takes O(log m) time
• Since we perform O(log m) operations for each of the n digits, the total time complexity is O(n × log m)
• Given that m = 1337 is a constant, this simplifies to O(n)

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space for variables mod, ans, and a
• The reversed iteration b[::-1] creates a reversed copy of array b, which takes O(n) space
• However, this can be optimized to O(1) by iterating from the end of the array without creating a copy
• Excluding the input array b, the space complexity is O(1) for the optimized version or O(n) if using array reversal

Common Pitfalls

1. Forgetting to Update the Base a After Each Iteration

One of the most common mistakes is forgetting to update a to a^10 mod 1337 after processing each digit. This update is crucial because each digit position represents a power that's 10 times larger than the previous one.

Incorrect Implementation:

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

This would incorrectly use the same base a for all digit positions, giving wrong results.

Solution: Always remember to update the base after processing each digit:

a = pow(a, 10, MOD)

2. Processing Digits in the Wrong Order

Another pitfall is processing the digits from left to right (most significant to least significant) without properly adjusting the logic. The algorithm relies on processing from right to left because we're building up from a^1 to a^10 to a^100, etc.

Incorrect Implementation:

def superPow(self, a: int, b: List[int]) -> int:
    MOD = 1337
    result = 1
  
    for digit in b:  # Wrong: processing from left to right
        result = (result * pow(a, digit, MOD)) % MOD
        a = pow(a, 10, MOD)
  
    return result

Solution: Either reverse the array or iterate backwards:

# Option 1: Reverse the array
for digit in reversed(b):
    # process digit

# Option 2: Iterate backwards
for i in range(len(b) - 1, -1, -1):
    digit = b[i]
    # process digit

3. Not Applying Modulo Operation Consistently

Failing to apply the modulo operation at every step can lead to integer overflow in languages with fixed integer sizes, or unnecessary large number computations.

Incorrect Implementation:

def superPow(self, a: int, b: List[int]) -> int:
    MOD = 1337
    result = 1
  
    for digit in reversed(b):
        result = result * pow(a, digit, MOD)  # Missing % MOD here
        a = pow(a, 10, MOD)
  
    return result % MOD  # Only applying mod at the end

While Python handles arbitrarily large integers, this approach is inefficient and in other languages could cause overflow.

Solution: Apply modulo after every multiplication to keep numbers small:

result = (result * pow(a, digit, MOD)) % MOD

4. Misunderstanding the Initial Value of result

Some might incorrectly initialize result to 0 or to a, thinking they need to start with the base or with nothing.

Incorrect Implementation:

result = 0  # Wrong: multiplication by 0 always gives 0
# or
result = a  # Wrong: this adds an extra factor of a

Solution: Always initialize result to 1 (the multiplicative identity):

result = 1

This ensures that the first multiplication correctly incorporates the first digit's contribution without adding extra factors.