Problem Description

The Leetcode problem Super Pow asks you to compute ab modulo 1337, where:

• a is a positive integer
• b is a large positive integer, but is provided as a list of digits (an array)

The key constraints are:

• The exponent b can be extremely large (hundreds or thousands of digits), so you cannot directly compute ab using built-in power functions or by converting b to an integer.
• You must return the result as ab % 1337.
• Efficient computation is required due to the potential size of b.

Thought Process

At first glance, it seems we could simply compute ab and take the modulus. However, since b can be extremely large, this is not practical or possible using standard integer types or naive methods.

The main challenge is to handle the huge exponent efficiently. We need to find a way to break down the computation such that we never have to deal with the entire exponent as a single integer. We should also leverage properties of modular arithmetic to keep intermediate results manageable.

This leads us to consider techniques like modular exponentiation and recursion, where we can process one digit of b at a time, combining results using mathematical properties.

Solution Approach

To solve this problem efficiently, we use the following insights:

• Modular Exponentiation: We can compute (ak) % m efficiently using the property (a * b) % m = ((a % m) * (b % m)) % m.
• Exponent Decomposition: If b is represented as an array of digits, say [d1, d2, ..., dn], then b = d1d2...dn (as a number). We can express ab in terms of the last digit and the rest:
  • ab = a(rest * 10 + last_digit) = (arest)10 * (alast_digit)
• Recursive Solution: We process the exponent array from the end (rightmost digit) and use recursion to combine the results.

The step-by-step algorithm is:

1. If the exponent array b is empty, return 1 (since any number to the power of 0 is 1).
2. Pop the last digit from b (let's call it last).
3. Recursively compute part1 = superPow(a, b) (with b now reduced).
4. Compute part2 = alast % 1337.
5. Combine using modular exponentiation: result = (pow(part1, 10, 1337) * part2) % 1337.

This approach ensures we never compute large powers directly, and we always work with manageable numbers.

Example Walkthrough

Let's walk through an example with a = 2 and b = [1, 0] (which represents 10).

1. First call: superPow(2, [1, 0])
2. Pop 0 (last digit), now b = [1]
3. Recursively call: superPow(2, [1])
4. Pop 1, now b = []
5. Base case: return 1
6. Now combine:
   • part1 = 1
   • part2 = 21 % 1337 = 2
   • result = (pow(1, 10, 1337) * 2) % 1337 = 2
7. Back to previous level:
   • part1 = 2
   • part2 = 20 % 1337 = 1
   • result = (pow(2, 10, 1337) * 1) % 1337 = 1024
8. So, 210 % 1337 = 1024

This shows how we break the problem into smaller pieces and combine them using modular arithmetic.

Time and Space Complexity

Brute-force approach:

• Would require computing ab directly, which is infeasible for large b due to time and memory limitations.

• Let n be the number of digits in b.
• Each recursive call processes one digit, so there are O(n) recursive calls.
• Each call computes pow(x, 10, 1337) and pow(a, digit, 1337), both of which are O(\log 10) and O(\log digit) (which are small, since digit ≤ 9).
• Overall time complexity: O(n)
• Space complexity: O(n) for the call stack (since recursion depth is at most n).

Summary

The Super Pow problem leverages properties of modular arithmetic and recursion to efficiently compute huge exponents modulo a small number, even when the exponent is too large to fit in standard types. By breaking the exponent digit-by-digit and combining results recursively, we avoid direct computation of large numbers and keep all intermediate values small and manageable. This approach is both elegant and efficient, making it possible to solve otherwise intractable cases with ease.

Code Implementation

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337

        def mod_pow(x, n):
            result = 1
            x = x % MOD
            while n:
                if n % 2:
                    result = (result * x) % MOD
                x = (x * x) % MOD
                n //= 2
            return result

        if not b:
            return 1

        last = b.pop()
        part1 = self.superPow(a, b)
        part2 = mod_pow(a, last)
        return (mod_pow(part1, 10) * part2) % MOD
      

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        const int MOD = 1337;
        if (b.empty()) return 1;
        int last = b.back();
        b.pop_back();
        int part1 = superPow(a, b);
        int part2 = mod_pow(a, last, MOD);
        return (mod_pow(part1, 10, MOD) * part2) % MOD;
    }
private:
    int mod_pow(int x, int n, int mod) {
        int result = 1;
        x %= mod;
        while (n) {
            if (n % 2) result = (result * x) % mod;
            x = (x * x) % mod;
            n /= 2;
        }
        return result;
    }
};
      

class Solution {
    private static final int MOD = 1337;
    public int superPow(int a, List<Integer> b) {
        if (b.size() == 0) return 1;
        int last = b.remove(b.size() - 1);
        int part1 = superPow(a, b);
        int part2 = modPow(a, last);
        return (modPow(part1, 10) * part2) % MOD;
    }

    private int modPow(int x, int n) {
        int result = 1;
        x %= MOD;
        while (n > 0) {
            if (n % 2 == 1) result = (result * x) % MOD;
            x = (x * x) % MOD;
            n /= 2;
        }
        return result;
    }
}
      

var superPow = function(a, b) {
    const MOD = 1337;
    function modPow(x, n) {
        let result = 1;
        x = x % MOD;
        while (n) {
            if (n % 2) result = (result * x) % MOD;
            x = (x * x) % MOD;
            n = Math.floor(n / 2);
        }
        return result;
    }
    if (b.length === 0) return 1;
    let last = b.pop();
    let part1 = superPow(a, b);
    let part2 = modPow(a, last);
    return (modPow(part1, 10) * part2) % MOD;
};