Super Pow - Solution & Explanation
Problem Statement
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] <= 9bdoes not contain leading zeros.
Approach Overview
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 1: Exponentiation by Squaring
This approach uses the technique of exponentiation by squaring. This method is efficient for computing large powers with a modular operation, reducing time complexity significantly compared to naive methods.
This C code implements exponentiation by squaring. It first initializes the result as 1. The main loop processes each digit in b, treating it as an exponent to the base a, and continually updates the result using modular arithmetic. This prevents overflow issues due to the large size of ab.
Complexity
Time Complexity: O(n) where n is the length of b.
Space Complexity: O(1).
Approach 2: Chinese Remainder Theorem Approach
This approach leverages the Chinese Remainder Theorem to make use of Fermat's Little Theorem for reducing the large exponent under the modulus 1337, which has prime factors 7 and 191.
This C solution applies Fermat's Little Theorem to reduce the exponent modulo 7 and 191, and combines results using the Chinese Remainder Theorem. The intermediary calculations are computed efficiently with helper functions.
Complexity
Time Complexity: O(n) where n is the length of b.
Space Complexity: O(1).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Exponentiation by Squaring | Time Complexity: O(n) where n is the length of b. |
| Chinese Remainder Theorem Approach | Time Complexity: O(n) where n is the length of b. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode SuperPow : Large Exp, ETF & Euler's Theorem | CP Course | EP 56.2 • Luv • 30,272 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Super Pow easy or hard?
How to solve Super Pow in O(n)?
What is the best approach for Super Pow?
What data structure is used in Super Pow?
What is the time complexity of Super Pow?
Super Pow Python or Java solution approach?
Is Super Pow asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Super Pow with our built-in code editor and test cases.
Practice on FleetCode