Super Pow - Leetcode Solution

The Super Pow problem on Leetcode is a mathematical problem that requires computing the value of a number raised to the power of another number, where the exponent is a large integer represented as an array of digits.

Problem Statement The problem statement is as follows:

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an array of digits. Example 1:

Input: a = 2, b = [3] Output: 8 Example 2:

Input: a = 2, b = [1,0] Output: 1024

Solution The solution to this problem involves modular arithmetic and the concept of modular exponentiation. The basic idea is to perform the exponentiation in a modular fashion, that is, by taking the remainder of the intermediate computations.

In order to compute a^b mod 1337, we can first compute a^b mod 1337 for smaller values of b using the properties of modular arithmetic. Specifically, if b is even, we can compute a^b mod 1337 as follows:

a^b mod 1337 = (a^(b/2) mod 1337) * (a^(b/2) mod 1337) mod 1337

Note that we are taking the remainder of the intermediate computations in order to keep the values small enough to fit in the memory. Similarly, if b is odd, we can use the following formula:

a^b mod 1337 = (a^(b-1) mod 1337) * (a mod 1337) mod 1337

Once we have computed a^b mod 1337 for smaller values of b, we can use the above formulas repeatedly to compute a^b mod 1337 for larger values of b.

In order to implement this algorithm efficiently, we can use a recursive function that takes in a, b, and the current value of a^b mod 1337. The function should return the final value of a^b mod 1337. Here is the implementation of the solution:

def superPow(a: int, b: List[int]) -> int: if not b: return 1

last_digit = b.pop()
return pow(a, last_digit, 1337) * pow(superPow(a, b), 10, 1337) % 1337

Explanation of the Solution The solution is based on recursion and the properties of modular arithmetic. The main idea is to break down the exponent into smaller values and compute the exponentiation for each smaller value.

The input to the function is a, which is the base, and b, which is an array of digits representing the large exponent. We start by checking if the exponent is empty. If it is empty, we return 1 since any number raised to the power of 0 is 1.

Next, we remove the last digit from the exponent and store it in the variable last_digit. We then compute pow(a, last_digit, 1337) which is a^last_digit mod 1337 using the built-in pow() function. This is the modular exponentiation of a^last_digit.

Next, we recursively call the function with the base a and the remaining digits of the exponent b. This computes a^(b/10) mod 1337 using the property discussed earlier. We then take the remainder of this intermediate computation using pow(...,10,1337) which is equivalent to multiplying by 10 and taking the remainder since 10 % 1337 = 10. Finally, we take the remainder of the product of the two intermediate computations using % 1337 and return it as the final result.

Complexity Analysis The time complexity of the solution is O(n) where n is the number of digits in the exponent. This is because we are performing a recursive binary search on the exponent and each level cuts the size of the exponent by half.

The space complexity of the solution is also O(n) since we are using a recursive function with a maximum depth of n. Additionally, we are using two intermediate values each of size n which gives us a total space complexity of O(2n).

Conclusion The Super Pow problem on Leetcode is a mathematical problem that requires computing the values of a number raised to the power of another number using modular arithmetic. The solution involves using a recursive function that breaks down the exponent into smaller values and computes the exponentiation for each smaller value. The time and space complexity of the solution are both O(n) where n is the number of digits in the exponent.

1