# Super Pow
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/super-pow)
Canonical: https://scaleengineer.com/dsa/problems/super-pow
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
---
## Problem
Your task is to calculate `ab` mod `1337` where `a` is a positive integer and `b` is an extremely large positive integer given in the form of an array.

**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

**Constraints:**

* `1 <= a <= 231 - 1`
* `1 <= b.length <= 2000`
* `0 <= b[i] <= 9`
* `b` does not contain leading zeros.

# Approaches
## Iterative Calculation by Processing Digits
This approach is based on the property of exponents `x^(10y+z) = (x^y)^10 * x^z`. We can process the digits of `b` from left to right. If we have already computed the result for a prefix of `b`, say `res = a^(b_prefix) % 1337`, and the next digit is `d`, the new number is `b_prefix * 10 + d`. The new result will be `a^(b_prefix * 10 + d) % 1337`, which simplifies to `( (a^(b_prefix))^10 * a^d ) % 1337`. This can be calculated as `( power(res, 10, 1337) * power(a, d, 1337) ) % 1337`. We can iterate through all digits of `b` and update the result accordingly.
**Time:** O(k), where `k` is the number of digits in `b`. The loop runs `k` times. Inside the loop, we call the `power` function with small, constant exponents (10 and a single digit d < 10). The complexity of `power(base, exp)` is `O(log exp)`, which is `O(1)` for constant exponents. Thus, the total time complexity is `O(k)`. · **Space:** O(1), as we only use a few variables to store intermediate results.
**Pros:** Simple to understand and implement.; Does not require advanced number theory concepts.; Generalizes to any modulus, not just 1337.
**Cons:** May be slightly less performant than a number-theory-based approach due to repeated modular exponentiation with a large modulus inside the loop, leading to a larger constant factor in its time complexity.
### Explanation
This approach works by processing the digits of the large exponent `b` one by one from left to right. The core idea relies on the mathematical property `x^(10y + z) = (x^y)^10 * x^z`.
Let's say we have processed a prefix of `b` and calculated `res = a^(prefix) % 1337`. When we consider the next digit `d`, the new exponent becomes `prefix * 10 + d`. The new result can be calculated as `a^(prefix * 10 + d) % 1337`, which is equivalent to `(a^(prefix * 10) * a^d) % 1337`. This further simplifies to `((a^prefix)^10 * a^d) % 1337`.
Since we already have `res = a^(prefix) % 1337`, the updated result is `(power(res, 10, 1337) * power(a, d, 1337)) % 1337`.
We start with a result of 1 (for an empty prefix) and iterate through all digits of `b`, updating the result in each step.
A helper function for modular exponentiation, `power(base, exp)`, is used to efficiently compute powers under a modulus. This function uses the binary exponentiation (or exponentiation by squaring) algorithm.
```java
class Solution {
    private int MOD = 1337;

    public int superPow(int a, int[] b) {
        if (a % MOD == 0) return 0;
        a %= MOD;
        int result = 1;
        for (int digit : b) {
            result = (power(result, 10) * power(a, digit)) % MOD;
        }
        return result;
    }

    // Computes (base^exp) % MOD using binary exponentiation
    private int power(int base, int exp) {
        int res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (int)((long)res * base % MOD);
            }
            base = (int)((long)base * base % MOD);
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Initialize `result = 1`.
2. Create a helper function `power(base, exp, mod)` for modular exponentiation using the binary exponentiation method.
3. Iterate through each digit `d` in the input array `b` from left to right.
4. In each iteration, update the `result` by applying the rule `a^(10*x + d) = (a^x)^10 * a^d`. The new result is calculated as `result = (power(result, 10, 1337) * power(a, d, 1337)) % 1337`.
5. After iterating through all digits, `result` will hold the final value of `a^b % 1337`.

## Number Theory Approach (CRT & Fermat's Little Theorem)
This approach leverages number theory to optimize the calculation. The modulus is `1337 = 7 * 191`. We can compute `a^b mod 7` and `a^b mod 191` separately and then combine the results using the Chinese Remainder Theorem (CRT). To compute `a^b mod p` (where `p` is prime), we use Fermat's Little Theorem, which states `x^(p-1) ≡ 1 (mod p)`. This means we only need the exponent `b` modulo `p-1`. So, we first compute `b % 6` and `b % 190` and then use these smaller exponents to find the result modulo 7 and 191, which are then combined to get the final answer.
**Time:** O(k), where `k` is the length of `b`. Computing `b` modulo `6` and `190` each takes `O(k)` time. The modular exponentiation and CRT steps take constant time with respect to `k`. Therefore, the overall time complexity is dominated by processing the digits of `b`. · **Space:** O(1), as only a constant amount of extra space is used.
**Pros:** More efficient in practice due to a smaller constant factor. The main loop to process `b` involves operations with small moduli (6 and 190), and the expensive modular exponentiation is done only a constant number of times.
**Cons:** Significantly more complex to understand and implement correctly.; Requires knowledge of number theory, including Fermat's Little Theorem and the Chinese Remainder Theorem.; The solution is tailored to the specific modulus `1337`. If the modulus changes, it must be re-factored, and modular inverses must be recalculated.
### Explanation
This advanced approach uses number theory to find the solution more efficiently. The modulus `1337` is not a prime number; it can be factored into `7 * 191`. This allows us to use the Chinese Remainder Theorem (CRT).
The problem of finding `x = a^b % 1337` is broken down into solving a system of two congruences:
1. `x ≡ a^b (mod 7)`
2. `x ≡ a^b (mod 191)`

To solve each congruence, we use Fermat's Little Theorem. This implies that the exponent `b` can be reduced modulo `p-1`. So, we need to compute `b % (7-1) = b % 6` and `b % (191-1) = b % 190`. The value of `b` modulo some number `m` can be found by iterating through its digits.
Once we have `res1 = a^b % 7` and `res2 = a^b % 191`, we use the CRT to combine them. We look for a number `x` that satisfies both congruences. The solution will be unique modulo `7 * 191 = 1337`.
The implementation requires pre-calculating the modular multiplicative inverse of `7` modulo `191`, which is `82`.
```java
class Solution {
    private final int MOD = 1337;

    public int superPow(int a, int[] b) {
        if (a % MOD == 0) return 0;

        // Calculate b mod phi(7)=6 and b mod phi(191)=190
        int b_mod_6 = getBModM(b, 6);
        if (b_mod_6 == 0) b_mod_6 = 6; // For b>=1, a^b = a^(phi) if b%phi=0

        int b_mod_190 = getBModM(b, 190);
        if (b_mod_190 == 0) b_mod_190 = 190;

        // Calculate res1 = a^b mod 7
        int res1 = power(a, b_mod_6, 7);
        
        // Calculate res2 = a^b mod 191
        int res2 = power(a, b_mod_190, 191);

        // Use Chinese Remainder Theorem to find the unique solution
        // x ≡ res1 (mod 7)
        // x ≡ res2 (mod 191)
        // From x = 7k + res1, we get 7k + res1 ≡ res2 (mod 191)
        // k ≡ (res2 - res1) * modInverse(7, 191) (mod 191)
        // The modular inverse of 7 mod 191 is 82.
        int k = (res2 - res1 + 191) % 191; // Handle negative result
        k = (int)((long)k * 82 % 191);
        
        return res1 + 7 * k;
    }

    // Computes b % m
    private int getBModM(int[] b, int m) {
        int rem = 0;
        for (int digit : b) {
            rem = (rem * 10 + digit) % m;
        }
        return rem;
    }

    // Computes (base^exp) % mod
    private int power(int base, int exp, int mod) {
        int res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (int)((long)res * base % mod);
            }
            base = (int)((long)base * base % mod);
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Factor the modulus: `1337 = 7 * 191`.
2. The problem `x = a^b % 1337` is split into a system of congruences: `x ≡ a^b (mod 7)` and `x ≡ a^b (mod 191)`.
3. To solve these, we use Fermat's Little Theorem, which reduces the exponent `b` modulo `p-1`. We need to compute `b % 6` and `b % 190`.
4. The remainders `b % m` are calculated by iterating through the digits of `b`: `rem = (rem * 10 + digit) % m`.
5. Handle the edge case where `b % (p-1) == 0`. The effective exponent should be `p-1`, not `0`.
6. Calculate `res1 = a^b (mod 7)` and `res2 = a^b (mod 191)` using the reduced exponents.
7. Combine `res1` and `res2` using the Chinese Remainder Theorem (CRT) to find the unique solution `x` modulo 1337.

# Solutions
### Java

```java
class Solution {
private
  final int mod = 1337;
public
  int superPow(int a, int[] b) {
    long ans = 1;
    for (int i = b.length - 1; i >= 0; --i) {
      ans = ans * qpow(a, b[i]) % mod;
      a = qpow(a, 10);
    }
    return (int)ans;
  }
private
  long qpow(long a, int n) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int superPow(int a, vector<int> &b) {
    using ll = long long;
    const int mod = 1337;
    ll ans = 1;
    auto qpow = [&](ll a, int n) {
      ll ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return (int)ans;
    };
    for (int i = b.size() - 1; ~i; --i) {
      ans = ans * qpow(a, b[i]) % mod;
      a = qpow(a, 10);
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def superPow ( self , a : int , b : List [ int ]) -> int : mod = 1337 ans = 1 for e in b [:: - 1 ]: ans = ans * pow ( a , e , mod ) % mod a = pow ( a , 10 , mod ) return ans
```