Domain 2MediumCORE

Super Pow

We need to compute $a^b mod 1337$. The input a fits in a standard integer ($1 le a le 2^{31}-1$), but b represents an extremely large number given as an array of digits (length up to 2000). Directly converting the digit list into an integer is impossible due to memory constraints and overflow risks. We must compute this using modular arithmetic properties without constructing the full exponent value in memory.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

372. Super Pow

Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 36.7%


Problem Breakdown

We need to compute abmod  1337a^b \mod 1337. The input a fits in a standard integer (1≤a≤231−11 \le a \le 2^{31}-1), but b represents an extremely large number given as an array of digits (length up to 2000). Directly converting the digit list into an integer is impossible due to memory constraints and overflow risks. We must compute this using modular arithmetic properties without constructing the full exponent value in memory.

Inputs:

  • a: Integer (1≤a≤231−11 \le a \le 2^{31}-1)
  • b: List of digits representing a large positive integer (length up to 2000).

Output:

  • The result modulo 1337.

Intuition

A brute-force approach would convert list b into a large integer and compute alarge_intmod  1337a^{\text{large\_int}} \mod 1337. This is infeasible because the exponent can have up to 2000 digits, making direct computation exponential or impossible.

The key insight relies on modular arithmetic properties:

  1. (x⋅y)mod  m=((xmod  m)⋅(ymod  m))mod  m(x \cdot y) \mod m = ((x \mod m) \cdot (y \mod m)) \mod m
  2. a(N×10+d)=(aN)10⋅ada^{(N \times 10 + d)} = (a^N)^{10} \cdot a^d.

We can process the digits of b from left to right (most significant digit first). If we have computed the result for the number formed by prefix digits, say value VV, and our current modular result is stored in res, then when we encounter the next digit dd:

  • The new exponent becomes 10×V+d10 \times V + d.
  • We can update res using: (pow(res, 10) * pow(a % m, d)) % m.

This allows us to maintain a running result that stays within bounds of standard integers at every step. By reducing the base modulo 1337 initially and applying modular exponentiation for each digit shift, we avoid overflow while maintaining mathematical correctness.

Approach

We will iterate through each digit in the array b:

  • Initialize our accumulator variable (res) to 1. This represents a0mod  ma^0 \mod m before processing any digits (the identity element).
  • For every digit d in b, we update res. The current number represented by processed digits is effectively multiplied by 10 and incremented by the new digit d. In modular exponentiation terms, this corresponds to raising the previous result (res) to the power of 10 (for the shift) and multiplying it by adigita^{\text{digit}}.
  • Formula: new_res = (pow(res, 10, MOD) * pow(a % MOD, digit)) % MOD.

This logic holds for every step. By reducing a modulo 1337 at the start, we ensure all intermediate calculations remain small and efficient. The loop processes digits from left to right, naturally building up the exponent value bb in chunks of decimal places without ever constructing the full number.

Complexity Analysis

  • Time: O(N)O(N) where NN is the length of array b. In each iteration, we perform modular exponentiation with a fixed small modulus (exponent max 10 or digit value). The cost per step is constant relative to input size because base and moduli are bounded. Total time scales linearly with number of digits in b.
  • Space: O(1)O(1) auxiliary space, as we only store the current result and a few variables.

Solution

from typing import List

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        
        # Reduce base 'a' immediately to keep numbers small within modular arithmetic rules
        a %= MOD
        
        res = 1
        
        for digit in b:
            # Update result based on the property: 
            # new_exponent_value = old_number * 10 + current_digit
            # We need (res^10) * base^(current_digit) % mod
            
            # pow(res, 10, MOD): raises previous modular result to power of place value shift
            res = (pow(res, 10, MOD) * pow(a, digit, MOD)) % MOD
            
        return res

Edge Cases Handled

  • Large a: We apply % MOD immediately on input a, preventing overflow before the loop. Python handles large integers automatically, but this keeps numbers small for efficiency and consistency with modular arithmetic properties.
  • Single Digit Array: The logic handles a single iteration correctly (shifts 0 times effectively if initialized to identity). For [d], it computes (1^10 * a^d) % MOD = a^d. Correct.
  • Result becoming 0/1: If intermediate result becomes 0 or 1, pow handles these cases naturally (e.g., aa is multiple of factors of 1337). The logic holds without special checks for zero base cases in modular arithmetic context here since we are building the exponent value effectively.
  • Leading Zeros: Constraint says none exist, but if they did (e.g., [0,5] -> number 5), pow(a, 0) is 1, then next step processes digit 5 correctly (a5a^5). The logic remains robust even with leading zeros mathematically.