Super Pow

MEDIUM

Description

Your task is to calculate a^b 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 <= 2³¹ - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b does not contain leading zeros.

Approaches

Checkout 2 different approaches to solve Super Pow. Click on different approaches to view the approach and algorithm in detail.

Iterative Calculation by Processing Digits

This approach is based on the property of exponents x^(10y+z) = (x^y)^10 * x^z. We can process the digits of b from left to right. If we have already computed the result for a prefix of b, say res = a^(b_prefix) % 1337, and the next digit is d, the new number is b_prefix * 10 + d. The new result will be a^(b_prefix * 10 + d) % 1337, which simplifies to ( (a^(b_prefix))^10 * a^d ) % 1337. This can be calculated as ( power(res, 10, 1337) * power(a, d, 1337) ) % 1337. We can iterate through all digits of b and update the result accordingly.

Algorithm

Initialize result = 1.
Create a helper function power(base, exp, mod) for modular exponentiation using the binary exponentiation method.
Iterate through each digit d in the input array b from left to right.
In each iteration, update the result by applying the rule a^(10*x + d) = (a^x)^10 * a^d. The new result is calculated as result = (power(result, 10, 1337) * power(a, d, 1337)) % 1337.
After iterating through all digits, result will hold the final value of a^b % 1337.

This approach works by processing the digits of the large exponent b one by one from left to right. The core idea relies on the mathematical property x^(10y + z) = (x^y)^10 * x^z. Let's say we have processed a prefix of b and calculated res = a^(prefix) % 1337. When we consider the next digit d, the new exponent becomes prefix * 10 + d. The new result can be calculated as a^(prefix * 10 + d) % 1337, which is equivalent to (a^(prefix * 10) * a^d) % 1337. This further simplifies to ((a^prefix)^10 * a^d) % 1337. Since we already have res = a^(prefix) % 1337, the updated result is (power(res, 10, 1337) * power(a, d, 1337)) % 1337. We start with a result of 1 (for an empty prefix) and iterate through all digits of b, updating the result in each step. A helper function for modular exponentiation, power(base, exp), is used to efficiently compute powers under a modulus. This function uses the binary exponentiation (or exponentiation by squaring) algorithm.

class Solution {
    private int MOD = 1337;

    public int superPow(int a, int[] b) {
        if (a % MOD == 0) return 0;
        a %= MOD;
        int result = 1;
        for (int digit : b) {
            result = (power(result, 10) * power(a, digit)) % MOD;
        }
        return result;
    }

    // Computes (base^exp) % MOD using binary exponentiation
    private int power(int base, int exp) {
        int res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (int)((long)res * base % MOD);
            }
            base = (int)((long)base * base % MOD);
            exp /= 2;
        }
        return res;
    }
}

Complexity Analysis

Time Complexity: O(k), where `k` is the number of digits in `b`. The loop runs `k` times. Inside the loop, we call the `power` function with small, constant exponents (10 and a single digit d < 10). The complexity of `power(base, exp)` is `O(log exp)`, which is `O(1)` for constant exponents. Thus, the total time complexity is `O(k)`.Space Complexity: O(1), as we only use a few variables to store intermediate results.

Pros and Cons

Pros:

Simple to understand and implement.
Does not require advanced number theory concepts.
Generalizes to any modulus, not just 1337.

Cons:

May be slightly less performant than a number-theory-based approach due to repeated modular exponentiation with a large modulus inside the loop, leading to a larger constant factor in its time complexity.

Code Solutions

Checking out 3 solutions in different languages for Super Pow. Click on different languages to view the code.

class Solution {
private
  final int mod = 1337;
public
  int superPow(int a, int[] b) {
    long ans = 1;
    for (int i = b.length - 1; i >= 0; --i) {
      ans = ans * qpow(a, b[i]) % mod;
      a = qpow(a, 10);
    }
    return (int)ans;
  }
private
  long qpow(long a, int n) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Super Pow

Algorithms:

Divide and Conquer

Patterns:

Math