LeetCode 372: Super Pow Solution

Master LeetCode problem 372 (Super Pow), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

372. Super Pow

Medium

Math Divide and Conquer

Problem Explanation

Explanation

To solve this problem, we can apply the modular exponentiation technique. The idea is to calculate the result iteratively by taking the mod value at each step to prevent overflow. By using the properties of modular arithmetic, we can optimize the computation.

Initialize a result variable to 1.
For each digit in the b array from right to left:
- Update the result by taking a to the power of the current digit modulo 1337.
- Multiply the result by the previous result raised to the power of 10 and modulo 1337.
Return the final result.

Time complexity: O(n) where n is the number of digits in the b array. Space complexity: O(1)

Solution Code

class Solution {
    public int superPow(int a, int[] b) {
        final int MOD = 1337;
        int result = 1;

        for (int digit : b) {
            result = pow(result, 10, MOD) * pow(a, digit, MOD) % MOD;
        }

        return result;
    }

    private int pow(int base, int exp, int mod) {
        base %= mod;
        int result = 1;

        for (int i = 0; i < exp; i++) {
            result = (result * base) % mod;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 372 (Super Pow)?

This page provides optimized solutions for LeetCode problem 372 (Super Pow) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 372 (Super Pow)?

The time complexity for LeetCode 372 (Super Pow) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 372 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 372 in Java, C++, or Python.

Back to LeetCode Solutions