
Description
Given two integers a
and an array of integers b
, we need to compute (a^b) % 1337
, where b
is treated as a large exponent represented as an array of digits. The problem aims to calculate a large power efficiently under modulo constraints.
The challenge lies in managing the potentially huge size of the exponent b
and ensuring that we perform the exponentiation in a time-efficient manner.
Intuition
Exponentiation with large numbers can lead to computational inefficiencies and potential overflows if done directly. Breaking down the problem, we recognize that powers of a
can be computed incrementally by breaking the array b
into smaller pieces and using properties of modular arithmetic. Specifically, using the property:
(a^b) % m = [(a^(b1)) % m * (a^(b2)) % m * ... ] % m
We can progressively compute powers of a
using smaller exponents derived from b
.
Approach
- Modular Arithmetic: Utilize the modulus 1337 at every step to prevent overflow and reduce computation. This leverages properties of modular exponentiation.
- Breaking Down Exponent: Traverse the array
b
from the least significant digit to the most significant digit, computing powers ofa
incrementally. For each digit inb
, we calculatea^digit % 1337
, updatea
asa^10 % 1337
for the next iteration, and multiply it by the previously calculated result. - Iterative Power Calculation: Implement a helper function
pow(a, b)
to calculate the powers under modulo conditions. Multiply the result for each digit iteratively while maintaining the modulus.
Complexity
Time Complexity:
O(n * log(a))
, where n
is the size of the array b
and log(a)
is the time taken to calculate a^b % 1337
for each b[i]
. This is because for each digit in b
, we compute a^digit % 1337
which takes logarithmic time with respect to a
.
Space Complexity:
O(1)
since the space used does not scale with input size beyond a few variables for computation.
Code
C++
class Solution {
public:
const int MOD = 1337;
int pow(int a, int b) {
int result = 1;
a %= MOD; // Taking mod to prevent overflow
for (int i = 0; i < b; i++) {
result = (result * a) % MOD;
}
return result;
}
int superPow(int a, vector& b) {
int result = 1;
for (int i = b.size() - 1; i >= 0; i--) {
result = (result * pow(a, b[i])) % MOD;
a = pow(a, 10); // Power up for the next iteration
}
return result;
}
};
Python
class Solution:
MOD = 1337
def pow(self, a: int, b: int) -> int:
result = 1
a %= self.MOD # Taking mod to prevent overflow
for _ in range(b):
result = (result * a) % self.MOD
return result
def superPow(self, a: int, b: list[int]) -> int:
result = 1
for i in range(len(b) - 1, -1, -1):
result = (result * self.pow(a, b[i])) % self.MOD
a = self.pow(a, 10) # Power up for the next iteration
return result
Java
class Solution {
private static final int MOD = 1337;
private int pow(int a, int b) {
int result = 1;
a %= MOD; // Taking mod to prevent overflow
for (int i = 0; i < b; i++) {
result = (result * a) % MOD;
}
return result;
}
public int superPow(int a, int[] b) {
int result = 1;
for (int i = b.length - 1; i >= 0; i--) {
result = (result * pow(a, b[i])) % MOD;
a = pow(a, 10); // Power up for the next iteration
}
return result;
}
}
JavaScript
/**
* @param {number} a
* @param {number[]} b
* @return {number}
*/
var superPow = function(a, b) {
const MOD = 1337;
const pow = (num, n) => {
let result = 1;
for (let index = 0; index < n; index++) {
result = result * num % MOD;
}
return result;
};
return b.reduceRight((result, n) => {
a %= MOD;
const powNum = result * pow(a, n) % MOD;
a = pow(a, 10);
return powNum;
}, 1);
};