In this guide, you will get 372. Super Pow LeetCode Solution with the best time and space complexity. The solution to Super Pow problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 – 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b does not contain leading zeros.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
372. Super Pow LeetCode Solution in C++
class Solution {
public:
int superPow(int a, vector<int>& b) {
int ans = 1;
a %= kMod;
for (const int i : b)
ans = modPow(ans, 10) * modPow(a, i) % kMod;
return ans;
}
private:
static constexpr int kMod = 1337;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
372. Super Pow LeetCode Solution in Java
class Solution {
public int superPow(int a, int[] b) {
int ans = 1;
a %= kMod;
for (final int i : b)
ans = modPow(ans, 10) * modPow(a, i) % kMod;
return ans;
}
private static final int kMod = 1337;
private int modPow(int x, int n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
} // code provided by PROGIEZ
372. Super Pow LeetCode Solution in Python
class Solution:
def superPow(self, a: int, b: list[int]) -> int:
kMod = 1337
ans = 1
for i in b:
ans = pow(ans, 10, kMod) * pow(a, i, kMod)
return ans % kMod # code by PROGIEZ
