372. Super Pow

Description

Given two integers a and an array of integers b, we need to compute (a^b) % 1337, where b is treated as a large exponent represented as an array of digits. The problem aims to calculate a large power efficiently under modulo constraints.

The challenge lies in managing the potentially huge size of the exponent b and ensuring that we perform the exponentiation in a time-efficient manner.

Intuition

Exponentiation with large numbers can lead to computational inefficiencies and potential overflows if done directly. Breaking down the problem, we recognize that powers of a can be computed incrementally by breaking the array b into smaller pieces and using properties of modular arithmetic. Specifically, using the property:

(a^b) % m = [(a^(b1)) % m * (a^(b2)) % m * ... ] % m

We can progressively compute powers of a using smaller exponents derived from b.

Approach

1. Modular Arithmetic: Utilize the modulus 1337 at every step to prevent overflow and reduce computation. This leverages properties of modular exponentiation.
2. Breaking Down Exponent: Traverse the array b from the least significant digit to the most significant digit, computing powers of a incrementally. For each digit in b, we calculate a^digit % 1337, update a as a^10 % 1337 for the next iteration, and multiply it by the previously calculated result.
3. Iterative Power Calculation: Implement a helper function pow(a, b) to calculate the powers under modulo conditions. Multiply the result for each digit iteratively while maintaining the modulus.

Complexity

Time Complexity:

O(n * log(a)), where n is the size of the array b and log(a) is the time taken to calculate a^b % 1337 for each b[i]. This is because for each digit in b, we compute a^digit % 1337 which takes logarithmic time with respect to a.

Space Complexity:

O(1) since the space used does not scale with input size beyond a few variables for computation.

Code

C++

class Solution {
public:
    const int MOD = 1337;

    int pow(int a, int b) {
        int result = 1;
        a %= MOD;  // Taking mod to prevent overflow
        for (int i = 0; i < b; i++) {
            result = (result * a) % MOD;
        }
        return result;
    }

    int superPow(int a, vector& b) {
        int result = 1;
        for (int i = b.size() - 1; i >= 0; i--) {
            result = (result * pow(a, b[i])) % MOD;
            a = pow(a, 10);  // Power up for the next iteration
        }
        return result;
    }
};

Python

class Solution:
    MOD = 1337

    def pow(self, a: int, b: int) -> int:
        result = 1
        a %= self.MOD  # Taking mod to prevent overflow
        for _ in range(b):
            result = (result * a) % self.MOD
        return result

    def superPow(self, a: int, b: list[int]) -> int:
        result = 1
        for i in range(len(b) - 1, -1, -1):
            result = (result * self.pow(a, b[i])) % self.MOD
            a = self.pow(a, 10)  # Power up for the next iteration
        return result

Java

class Solution {
    private static final int MOD = 1337;

    private int pow(int a, int b) {
        int result = 1;
        a %= MOD;  // Taking mod to prevent overflow
        for (int i = 0; i < b; i++) {
            result = (result * a) % MOD;
        }
        return result;
    }

    public int superPow(int a, int[] b) {
        int result = 1;
        for (int i = b.length - 1; i >= 0; i--) {
            result = (result * pow(a, b[i])) % MOD;
            a = pow(a, 10);  // Power up for the next iteration
        }
        return result;
    }
}

JavaScript

/**
 * @param {number} a
 * @param {number[]} b
 * @return {number}
 */
var superPow = function(a, b) {
	const MOD = 1337;
	const pow = (num, n) => {
		let result = 1;
		for (let index = 0; index < n; index++) {
			result = result * num % MOD;
		}
		return result;
	};

	return b.reduceRight((result, n) => {
		a %= MOD;
		const powNum = result * pow(a, n) % MOD;

		a = pow(a, 10);
		return powNum;
	}, 1);
};