Watch 10 video solutions for Super Pow, a medium level problem involving Math, Divide and Conquer. This walkthrough by Sahil & Sarra has 656,557 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example 1:
Input: a = 2, b = [3] Output: 8
Example 2:
Input: a = 2, b = [1,0] Output: 1024
Example 3:
Input: a = 1, b = [4,3,3,8,5,2] Output: 1
Constraints:
1 <= a <= 231 - 11 <= b.length <= 20000 <= b[i] <= 9b does not contain leading zeros.Problem Overview: You are given an integer a and a very large exponent b represented as an array of digits. The task is to compute a^b % 1337. Since b can contain hundreds of digits, directly converting it into an integer or computing the full power is impossible due to overflow and performance limits.
Approach 1: Exponentiation by Squaring with Digit Decomposition (Time: O(n log 10), Space: O(1))
The key idea is to process the exponent digit by digit instead of forming the entire number. If b is represented as digits, the property a^(xy) = (a^x)^10 * a^y helps break the computation into manageable pieces. Iterate through the digits of b. For each digit, update the result as result = pow(result, 10) * pow(a, digit) % 1337. Both pow operations are computed using fast modular exponentiation (also called exponentiation by squaring), which runs in O(log k) time. Since each digit is at most 9, the exponent is tiny, making the total runtime roughly linear in the number of digits. This method relies heavily on math properties and the classic divide and conquer technique used in fast exponentiation.
Approach 2: Chinese Remainder Theorem Approach (Time: O(n log m), Space: O(1))
The modulus 1337 factors into 7 × 191. Instead of computing the result directly modulo 1337, compute a^b % 7 and a^b % 191 separately. Each subproblem is smaller and can be solved with modular exponentiation while processing the exponent digits just like the previous approach. Once both values are known, combine them using the Chinese Remainder Theorem to reconstruct the result modulo 1337. This technique leverages number theory from math and modular arithmetic. It is especially useful when the modulus factors into smaller primes, allowing you to reduce computational complexity in modular operations.
Recommended for interviews: The exponent digit decomposition with exponentiation by squaring is the approach most interviewers expect. It directly shows that you understand modular exponentiation and how to handle extremely large exponents represented as arrays. Mentioning the Chinese Remainder Theorem demonstrates deeper number theory knowledge, but the first approach is simpler to implement and easier to reason about under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Exponentiation by Squaring with Digit Decomposition | O(n log 10) ≈ O(n) | O(1) | General case when exponent is given as digits and modulus is fixed |
| Chinese Remainder Theorem | O(n log m) | O(1) | When modulus can be factorized into smaller primes for easier modular computation |