Super Pow solution and explanation
Google
9 more videos on this problem
Leetcode SuperPow : Large Exp, ETF & Euler's Theorem | CP Course | EP 56.2Luv · 9:56 · 30K views
372. Super Pow | LEETCODE MEDIUM | MODULAR ARITHMETICcode Explainer · 10:15 · 3K views
Leetcode 372. Super PowKacy Codes · 10:27 · 2K views
Leetcode solving: 372. Super PowMath Geeks · 4:25 · 999 views
Leetcode Question 372 "Super Pow" in JavaGhumman Tech · 6:45 · 966 views
Super Pow (LeetCode 372) | Fast Modular Exponentiation with φ(n) OptimizationYash Poonia · 23:54 · 798 views
Super Pow (Medium), Leetcode, C++H William Polenz · 15:21 · 548 views
LEETCODE 372:Unlocking Exponentiation: Mastering LeetCode's 372 - Super Powleetcode blind 75 · 4:17 · 427 views
372. Super Pow - Python Programming Interview Question Facebook Amazon Apple Netflix GoogleLearn with Amine · 3:17 · 372 views
Super Pow (LeetCode 372) — Intuition, Optimized Solution & Step-by-Step Codeplacement time · 38:10 · 354 views
The problem
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.
def super_pow(a, b):
mod = 1337
result = 1
for digit in b:
result = pow(result, 10, mod) * pow(a, digit, mod) % mod
return result
a = 2
b = [1, 0]
print(super_pow(a, b)) # Output: 1024import java.util.List;
public class SuperPow {
public static int superPow(int a, List<Integer> b) {
int mod = 1337;
int result = 1;
for (int digit : b) {
result = powMod(result, 10, mod) * powMod(a, digit, mod) % mod;
}
return result;
}
private static int powMod(int x, int y, int mod) {
int res = 1;
for (int i = 0; i < y; i++) {
res = (res * x) % mod;
}
return res;
}
public static void main(String[] args) {
List<Integer> b = List.of(1, 0);
System.out.println(superPow(2, b)); // Output: 1024
}
}#include <iostream>
#include <vector>
using namespace std;
int modExp(int a, vector<int>& b, int mod) {
int res = 1;
for (int i = 0; i < b.size(); ++i) {
res = (res * res) % mod;
for (int j = 0; j < b[i]; ++j) {
res = (res * a) % mod;
}
}
return res;
}
int main() {
int a = 2;
vector<int> b = {1, 0};
cout << modExp(a, b, 1337) << endl;
return 0;
}function superPow(a, b) {
const mod = 1337;
let result = 1;
for (let digit of b) {
result = (modularExponentiation(result, 10, mod) * modularExponentiation(a, digit, mod)) % mod;
}
return result;
}
function modularExponentiation(x, y, mod) {
let res = 1;
for (let i = 0; i < y; i++) {
res = (res * x) % mod;
}
return res;
}
const a = 2;
const b = [1, 0];
console.log(superPow(a, b)); // Output: 1024#include <stdio.h>
int modExp(int a, int* b, int bSize, int mod) {
int res = 1;
for (int i = 0; i < bSize; ++i) {
res = (res * res) % mod;
res = (res * res) % mod; // Square twice for proper handling of high powers
for (int j = 0; j < b[i]; ++j) {
res = (res * a) % mod;
}
}
return res;
}
int main() {
int a = 2;
int b[] = {1, 0};
int bSize = sizeof(b) / sizeof(b[0]);
int result = modExp(a, b, bSize, 1337);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class SuperPow {
public static int SuperPowCalc(int a, List<int> b) {
int mod = 1337;
int result = 1;
foreach (int digit in b) {
result = PowMod(result, 10, mod) * PowMod(a, digit, mod) % mod;
}
return result;
}
private static int PowMod(int x, int y, int mod) {
int res = 1;
for (int i = 0; i < y; i++) {
res = (res * x) % mod;
}
return res;
}
public static void Main(string[] args) {
List<int> b = new List<int> {1, 0};
Console.WriteLine(SuperPowCalc(2, b)); // Output: 1024
}
}This Python function uses Python's built-in pow function to compute ab % mod using iterative squaring for the large integer array b. This implementation leverages Python's efficient handling of large integers in modular arithmetic.
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.
def super_pow(a, b):
def pow_mod(x, y, mod):
result = 1
x %= mod
while y:
if y % 2:
result = (result * x) % mod
x = (x * x) % mod
y //= 2
return result
m1, m2 = 7, 191
r1, r2 = 1, 1
for digit in b:
r1 = pow_mod(r1, 10, m1) * pow_mod(a, digit, m1) % m1
r2 = pow_mod(r2, 10, m2) * pow_mod(a, digit, m2) % m2
result = (r1 * 191 * 183 + r2 * 7 * 55) % 1337
return result
b = [1, 0]
result = super_pow(2, b)
print(result) # Output: 1024import java.util.List;
public class SuperPow {
public static int superPow(int a, List<Integer> b) {
int m1 = 7, m2 = 191;
int r1 = 1, r2 = 1;
for (int digit : b) {
r1 = powMod(r1, 10, m1) * powMod(a, digit, m1) % m1;
r2 = powMod(r2, 10, m2) * powMod(a, digit, m2) % m2;
}
return (r1 * 191 * 183 + r2 * 7 * 55) % 1337;
}
private static int powMod(int x, int y, int mod) {
int res = 1;
x %= mod;
while (y > 0) {
if (y % 2 == 1) res = (res * x) % mod;
x = (x * x) % mod;
y /= 2;
}
return res;
}
public static void main(String[] args) {
List<Integer> b = List.of(1, 0);
System.out.println(superPow(2, b)); // Output: 1024
}
}#include <iostream>
#include <vector>
using namespace std;
int powMod(int a, int exp, int mod) {
int result = 1;
a %= mod;
while (exp > 0) {
if (exp % 2 == 1) result = (result * a) % mod;
a = (a * a) % mod;
exp /= 2;
}
return result;
}
int superPow(int a, vector<int>& b) {
int m1 = 7, m2 = 191;
int r1 = 1, r2 = 1;
for (int digit : b) {
r1 = powMod(r1, 10, m1) * powMod(a, digit, m1) % m1;
r2 = powMod(r2, 10, m2) * powMod(a, digit, m2) % m2;
}
int result = (r1 * 191 * 183 + r2 * 7 * 55) % 1337;
return result;
}
int main() {
int a = 2;
vector<int> b = {1, 0};
cout << superPow(a, b) << endl;
return 0;
}function superPow(a, b) {
function powMod(x, y, mod) {
let result = 1;
x %= mod;
while (y > 0) {
if (y % 2 === 1) result = (result * x) % mod;
x = (x * x) % mod;
y = Math.floor(y / 2);
}
return result;
}
const m1 = 7, m2 = 191;
let r1 = 1, r2 = 1;
for (let digit of b) {
r1 = powMod(r1, 10, m1) * powMod(a, digit, m1) % m1;
r2 = powMod(r2, 10, m2) * powMod(a, digit, m2) % m2;
}
return (r1 * 191 * 183 + r2 * 7 * 55) % 1337;
}
const a = 2;
const b = [1, 0];
console.log(superPow(a, b)); // Output: 1024#include <stdio.h>
int powMod(int a, int exp, int mod) {
int result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * a) % mod;
}
a = (a * a) % mod;
exp /= 2;
}
return result;
}
int superPow(int a, int* b, int bSize) {
int m1 = 7, m2 = 191;
int r1 = 1, r2 = 1;
for (int i = 0; i < bSize; ++i) {
r1 = powMod(r1, 10, m1) * powMod(a, b[i], m1) % m1;
r2 = powMod(r2, 10, m2) * powMod(a, b[i], m2) % m2;
}
// Use the results from Chinese Remainder Theorem to find the final result
int result = (r1 * 191 * 183 + r2 * 7 * 55) % 1337;
return result;
}
int main() {
int a = 2;
int b[] = {1, 0};
int bSize = sizeof(b) / sizeof(b[0]);
int result = superPow(a, b, bSize);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class SuperPow {
public static int SuperPowCalc(int a, List<int> b) {
int m1 = 7, m2 = 191;
int r1 = 1, r2 = 1;
foreach (int digit in b) {
r1 = PowMod(r1, 10, m1) * PowMod(a, digit, m1) % m1;
r2 = PowMod(r2, 10, m2) * PowMod(a, digit, m2) % m2;
}
int result = (r1 * 191 * 183 + r2 * 7 * 55) % 1337;
return result;
}
private static int PowMod(int x, int y, int mod) {
int res = 1;
x %= mod;
while (y > 0) {
if (y % 2 == 1) res = (res * x) % mod;
x = (x * x) % mod;
y /= 2;
}
return res;
}
public static void Main(string[] args) {
List<int> b = new List<int> {1, 0};
Console.WriteLine(SuperPowCalc(2, b)); // Output: 1024
}
}This Python function reduces the calculation using prime factors 7 and 191, combining results using the Chinese Remainder Theorem for efficient computation of large integers under modulus.
Time Complexity: O(n) where n is the length of b.
Space Complexity: O(1).
Approach 3: Default Approach
function superPow(a: number, b: number[]): number {
let ans = 1;
const mod = 1337;
const qpow = (a: number, n: number): number => {
let ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans = Number((BigInt(ans) * BigInt(a)) % BigInt(mod));
}
a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
}
return ans;
};
for (let i = b.length - 1; ~i; --i) {
ans = Number((BigInt(ans) * BigInt(qpow(a, b[i]))) % BigInt(mod));
a = qpow(a, 10);
}
return ans;
}func superPow(a int, b []int) int {
const mod int = 1337
ans := 1
qpow := func(a, n int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
for i := len(b) - 1; i >= 0; i-- {
ans = ans * qpow(a, b[i]) % mod
a = qpow(a, 10)
}
return ans
}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 | – |
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 |
Frequently asked questions
Is Super Pow easy or hard?
Super Pow is considered a Medium difficulty problem. The implementation is short, but recognizing how to handle a very large exponent using modular exponentiation and digit decomposition requires solid understanding of math and divide-and-conquer techniques.
How to solve Super Pow in O(n)?
Iterate through the digits of the exponent array and repeatedly update the result using the formula result = pow(result, 10) * pow(a, digit) % 1337. Both powers are computed using fast modular exponentiation. This keeps every step constant time, resulting in overall O(n) complexity.
What is the best approach for Super Pow?
Exponentiation by squaring with digit decomposition is the most practical approach. It processes the exponent array one digit at a time and repeatedly applies modular exponentiation. The method runs in O(n) time where n is the number of digits in b and uses O(1) extra space.
What data structure is used in Super Pow?
The problem mainly uses arrays to store the digits of the exponent and mathematical techniques like modular exponentiation. No advanced data structures are required; the focus is on number theory and efficient power computation.
What is the time complexity of Super Pow?
The optimal solution runs in O(n) time where n is the number of digits in the exponent array. Each step performs fast modular exponentiation on small exponents (≤10), which takes constant time in practice. Space complexity remains O(1).
Super Pow Python or Java solution approach?
Both Python and Java implementations follow the same pattern: implement a fast modular power function and process the exponent digits iteratively. Each iteration raises the current result to the power of 10, multiplies by a^digit, and takes modulo 1337.
Is Super Pow asked at Google, Amazon, or Meta?
Variants of modular exponentiation and large-number power problems appear in interviews at companies like Google and Amazon. They test knowledge of number theory, modular arithmetic, and divide-and-conquer algorithms such as fast exponentiation.