LeetCode 372: Super Pow Solution in Python – A Step-by-Step Guide

What Is LeetCode 372: Super Pow?

In LeetCode 372: Super Pow, you’re given an integer a (the base) and an array b (digits of the exponent), and your task is to compute (a^b \mod 1337), where (b) represents a large exponent (e.g., (b = [1, 2, 3]) means (b = 123)). The modulus 1337 is fixed, and the exponent can be huge, requiring efficient computation. For example, with a = 2 and b = [3], compute (2^3 \mod 1337 = 8 \mod 1337 = 8); with b = [1, 0], compute (2^{10} \mod 1337 = 1024 \mod 1337 = 1024).

Problem Statement

• Input: Integer a (base), array b (exponent digits).
• Output: Integer—\(a^b \mod 1337\).
• Rules:
• \(b\) represents a large exponent (e.g., \(b = [1, 2, 3] \rightarrow 123\)).
• Compute result modulo 1337.
• Handle large exponents efficiently.

Constraints

• 1 <= a <= 2³¹ - 1
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• \(b\) has no leading zeros.

Examples

• Input: a = 2, b = [3]
• Output: 8
• Why: \(2^3 = 8\), \(8 \mod 1337 = 8\).
• Input: a = 2, b = [1, 0]
• Output: 1024
• Why: \(2^{10} = 1024\), \(1024 \mod 1337 = 1024\).
• Input: a = 2147483647, b = [2, 0, 0]
• Output: 1198
• Why: \(2147483647^{200} \mod 1337 = 1198\) (computed efficiently).

Understanding the Problem: Powering Up Modulo 1337

To solve LeetCode 372: Super Pow in Python, we need to compute (a^b \mod 1337), where (b) is a large exponent given as an array of digits (e.g., (b = [1, 2, 3] \rightarrow 123)). A naive approach—computing (a^b) directly and then modding—would overflow due to the exponent’s size (up to (10^{2000})). Instead, we’ll use modular arithmetic properties:

• Best Solution (Modular Exponentiation with Divide-and-Conquer): O(n) time, O(1) space—fast and recursive.
• Alternative Solution (Naive Exponentiation with Optimization): O(n * log b) time, O(1) space—simpler but slower.

Let’s dive into the Best Solution—modular exponentiation with divide-and-conquer—and break it down step-by-step.

Best Solution: Modular Exponentiation with Divide-and-Conquer

Why This Is the Best Solution

The modular exponentiation with divide-and-conquer approach is the top choice because it’s highly efficient—O(n) time, where n is the length of the exponent array—and uses O(1) space beyond recursion, leveraging Euler’s theorem and modular properties to handle large exponents. It breaks the exponent into digits, recursively computes powers, and applies modulo at each step to prevent overflow. It’s like building a giant power tower digit by digit, keeping it manageable with a magic modulo mirror—smart and scalable!

How It Works

Here’s the strategy:

• Step 1: Define Constants:
• Modulus = 1337.
• Step 2: Modular Exponentiation Helper:
• pow(base, exp, mod): Computes \(base^{exp} \mod mod\) efficiently.
• Use divide-and-conquer: \(a^b = (a^{b//2})^2\) if b even, \(a * (a^{b-1})\) if odd.
• Step 3: Process Exponent Array:
• Treat \(b = [b_0, b_1, ..., b_{n-1}]\) as \(b = b_0 * 10^{n-1} + b_1 * 10^{n-2} + ... + b_{n-1}\).
• Recursively: \(a^b = a^{b_0 * 10^{n-1} } * a^{b_1 * 10^{n-2} } * ... * a^{b_{n-1} }\).
• Step 4: Apply Modulo:
• Use \(1337 = 7 * 191\), but directly mod 1337 suffices with properties.
• Step 5: Return:
• Final result mod 1337.

Step-by-Step Example

Example: a = 2, b = [1, 2, 3]

• Step 1: \(b = 123\), modulus = 1337.
• Step 2: Define pow(2, exp, 1337):
• \(2^1 = 2\), \(2^2 = 4\), \(2^4 = 16\), etc., mod 1337.
• Step 3: Compute \(2^{123}\):
• \(123 = 1 * 10^2 + 2 * 10^1 + 3 * 10^0\).
• Recursively:
• \(2^{123} = 2^{100} * 2^{20} * 2^3\).
• \(2^3 = 8\).
• \(2^{10} = 1024\), \(2^{20} = (2^{10})^2 = 1024^2 \mod 1337 = 121\).
• \(2^{100} = (2^{10})^{10} = 1024^{10} \mod 1337 = 1231\) (computed via pow).
• Combine: \(2^{100} * 2^{20} * 2^3 = 1231 * 121 * 8 \mod 1337\).
• Step 4: Modular steps:
• \(1231 * 121 = 148951 \mod 1337 = 1125\).
• \(1125 * 8 = 9000 \mod 1337 = 252\).
• Result: 252.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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

        # Step 1: Modular exponentiation helper
        def pow(base, exp, mod):
            if exp == 0:
                return 1
            if exp == 1:
                return base % mod
            half = pow(base, exp // 2, mod)
            if exp % 2 == 0:
                return (half * half) % mod
            else:
                return (half * half * base) % mod

        # Step 2: Process exponent array recursively
        def super_pow(a, b):
            if not b:
                return 1
            last_digit = b.pop()
            part1 = pow(a, last_digit, MOD)
            part2 = pow(super_pow(a, b), 10, MOD)
            return (part1 * part2) % MOD

        # Step 3: Start computation
        return super_pow(a % MOD, b)

• Line 4: Define modulus.
• Line 7-15: pow helper:
• Line 8-10: Base cases.
• Line 11-15: Divide-and-conquer exponentiation.
• Line 18-23: super_pow:
• Line 19-20: Base case for empty array.
• Line 21-23: Process last digit, recurse, combine.
• Line 26: Start with \(a \mod 1337\).
• Time Complexity: O(n)—n digits processed, each with constant-time pow.
• Space Complexity: O(1)—recursion stack (can be O(n) worst case).

This is a modular power maestro!

Alternative Solution: Naive Exponentiation with Optimization

Why an Alternative Approach?

The naive exponentiation with optimization approach offers a simpler take—O(n * log b) time, O(1) space—converting the array to a full exponent first, then computing with modular steps. It’s more straightforward but slower due to explicit exponent construction. It’s like raising the power step-by-step, keeping it in check with modulo—basic but educational!

How It Works

• Step 1: Convert b array to integer exponent.
• Step 2: Use modular exponentiation iteratively.
• Step 3: Return result mod 1337.

Step-by-Step Example

Example: a = 2, b = [1, 2, 3]

• Step 1: \(b = 123\).
• Step 2: \(2^{123} \mod 1337\):
• Binary: 123 = 1111011.
• \(2^1 = 2\), \(2^2 = 4\), \(2^4 = 16\), \(2^8 = 256\), \(2^{16} = 65536 \mod 1337 = 122\).
• \(2^{32} = 122^2 = 14884 \mod 1337 = 94\).
• \(2^{64} = 94^2 = 8836 \mod 1337 = 819\).
• Combine: \(2^{64} * 2^{32} * 2^{16} * 2^8 * 2^2 * 2^1\).
• Step 3: Compute iteratively → 252.
• Result: 252.

Code for Naive Approach

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

        # Step 1: Convert b to integer
        exp = 0
        for digit in b:
            exp = exp * 10 + digit

        # Step 2: Modular exponentiation
        result = 1
        base = a % MOD
        while exp > 0:
            if exp % 2 == 1:
                result = (result * base) % MOD
            base = (base * base) % MOD
            exp //= 2

        return result

• Line 6-8: Build exponent from array.
• Line 11-17: Iterative exponentiation.
• Time Complexity: O(n + log b)—n for array, log b for exponentiation.
• Space Complexity: O(1)—few variables.

It’s a step-by-step power builder!

Comparing the Two Solutions

• Divide-and-Conquer (Best):
• Pros: O(n) time, O(1) space, fast and direct.
• Cons: Recursive complexity.
• Naive (Alternative):
• Pros: O(n * log b) time, O(1) space, simpler logic.
• Cons: Slower for large exponents.

Divide-and-conquer wins for efficiency.

Additional Examples and Edge Cases

• a = 1, b = [4, 3]: 1.
• a = 2, b = [0]: 1.
• a = 10, b = [1, 0, 0]: 1129.

Both handle these perfectly.

Complexity Breakdown

• Divide-and-Conquer: Time O(n), Space O(1).
• Naive: Time O(n * log b), Space O(1).

Divide-and-conquer’s speed shines.

Key Takeaways

• Divide-and-Conquer: Break and mod!
• Naive: Build and power!
• Modulo: Keep it small.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Power Up

LeetCode 372: Super Pow in Python is a modular math adventure. The divide-and-conquer approach powers up with speed, while naive offers a clear path. Want more math fun? Try LeetCode 50: Pow(x, n) or LeetCode 326: Power of Three. Ready to compute? Head to Solve LeetCode 372 on LeetCode and supercharge that pow today!