372. Super Pow – Leetcode Solutions

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

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        # Define the modulus
        MOD = 1337
        
        # Helper function to perform modular exponentiation
        def mod_exp(base, exp, mod):
            return pow(base, exp, mod)
        
        # Recursive function to calculate a^b mod 1337 where b is given as a list of digits
        def super_pow_recursive(a, b):
            if not b:
                return 1  # Base case: a^0 = 1
            
            # Get the last digit of b
            last_digit = b.pop()
            
            # Compute a^(b // 10) mod 1337
            part1 = super_pow_recursive(a, b)
            part1 = mod_exp(part1, 10, MOD)
            
            # Compute a^last_digit mod 1337
            part2 = mod_exp(a, last_digit, MOD)
            
            # Combine the two parts
            return (part1 * part2) % MOD
        
        # Ensure 'a' is within the modulus before starting
        a %= MOD
        return super_pow_recursive(a, b)

class Solution {
public:
    // Helper function to perform modular exponentiation
    int modPow(int a, int k, int mod) {
        int result = 1;
        a %= mod; // Take a mod initially to keep it small
        while (k > 0) {
            if (k % 2 == 1) {
                result = (result * a) % mod;
            }
            a = (a * a) % mod;
            k /= 2;
        }
        return result;
    }

    int superPow(int a, vector<int>& b) {
        const int mod = 1337;
        a %= mod; // Keep a within bounds of mod to start
        
        int result = 1;
        // Process each digit in the array b from the end to the beginning
        for (int i = b.size() - 1; i >= 0; i--) {
            // Calculate the power contribution of the current digit
            result = (result * modPow(a, b[i], mod)) % mod;
            // Prepare a for the next power of 10
            a = modPow(a, 10, mod);
        }
        return result;
    }
};

var superPow = function(a, b) {
    // Modulus as per the problem requirement
    const MOD = 1337;

    // Helper function to compute a^k % MOD using fast modular exponentiation
    function modPow(x, n, mod) {
        let result = 1;
        x = x % mod;
        while (n > 0) {
            if (n % 2 === 1) {
                result = (result * x) % mod;
            }
            x = (x * x) % mod;
            n = Math.floor(n / 2);
        }
        return result;
    }

    // Recursive function to process the exponent array b
    function recursivePow(a, b) {
        if (b.length === 0) return 1;  // Base case: no exponent means 1
        const lastDigit = b.pop(); // Get the last digit of the array `b`

        // Calculate part1 as (a^lastDigit) % MOD
        let part1 = modPow(a, lastDigit, MOD);

        // Calculate part2 as ((a^10)^(b/10)) % MOD
        let part2 = modPow(recursivePow(a, b), 10, MOD);

        // Combine the results for final modulus
        return (part1 * part2) % MOD;
    }

    // Call the recursive function
    return recursivePow(a, b);
};

class Solution {
    // Define a constant for modulo 1337 as required by the problem.
    private static final int MOD = 1337;
    
    // Main function to compute a^b % 1337 where b is given as an array of digits.
    public int superPow(int a, int[] b) {
        // Reduce a modulo 1337 initially to simplify computations
        a = a % MOD;
        return superPowHelper(a, b, b.length - 1);
    }
    
    // Helper function to recursively compute the result
    private int superPowHelper(int a, int[] b, int idx) {
        // Base case: if index is less than zero, we return 1 (a^0 % MOD)
        if (idx < 0) {
            return 1;
        }
        
        // Calculate a^(b[idx]) % MOD
        int lastDigitPower = modPow(a, b[idx]);
        
        // Calculate ((a^10)^(remaining b digits)) % MOD
        int remainingPower = modPow(superPowHelper(a, b, idx - 1), 10);
        
        // Combine the two results using modular multiplication
        return (lastDigitPower * remainingPower) % MOD;
    }
    
    // Function to calculate (base^exponent) % MOD using modular exponentiation
    private int modPow(int base, int exponent) {
        int result = 1;
        base = base % MOD;  // Reduce base modulo MOD
        while (exponent > 0) {
            // If exponent is odd, multiply result with base
            if (exponent % 2 == 1) {
                result = (result * base) % MOD;
            }
            // Square the base and reduce exponent by half
            base = (base * base) % MOD;
            exponent /= 2;
        }
        return result;
    }
}