Super Pow

medium math modular pow

Problem

Compute a^b mod 1337 where b is given as a non-empty array of digits (most significant first).

Inputa = 2, b = [1, 0]

Output1024

Horner: result starts at 1, then for each digit d → result = (result^10 · a^d) mod 1337.

b (digits)

MOD = 1337

def super_pow(a, b):
    a %= MOD
    res = 1
    for d in b:
        res = pow(res, 10, MOD) * pow(a, d, MOD) % MOD
    return res

const MOD = 1337;
function modpow(x, n) {
  x %= MOD;
  let r = 1;
  while (n > 0) {
    if (n & 1) r = (r * x) % MOD;
    x = (x * x) % MOD;
    n >>= 1;
  }
  return r;
}
function superPow(a, b) {
  a %= MOD;
  let res = 1;
  for (const d of b) {
    res = (modpow(res, 10) * modpow(a, d)) % MOD;
  }
  return res;
}

class Solution {
    static final int MOD = 1337;
    int modpow(int x, int n) {
        x %= MOD; long r = 1, b = x;
        while (n > 0) {
            if ((n & 1) == 1) r = r * b % MOD;
            b = b * b % MOD; n >>= 1;
        }
        return (int) r;
    }
    public int superPow(int a, int[] b) {
        a %= MOD;
        long res = 1;
        for (int d : b) res = (long) modpow((int) res, 10) * modpow(a, d) % MOD;
        return (int) res;
    }
}

const int MOD = 1337;
int modpow(int x, int n) {
    x %= MOD; long r = 1, b = x;
    while (n > 0) {
        if (n & 1) r = r * b % MOD;
        b = b * b % MOD; n >>= 1;
    }
    return (int) r;
}
int superPow(int a, vector<int>& b) {
    a %= MOD;
    long res = 1;
    for (int d : b) res = (long) modpow(res, 10) * modpow(a, d) % MOD;
    return (int) res;
}

Explanation

The exponent b is given as an array of digits, which means it can be enormous, far too big to turn into one integer. The fix is to process it one digit at a time using Horner's method for reading numbers left to right.

Reading b left to right, a number like [1, 0] means 10 = 1*10 + 0. Raising a to that exponent, we can fold the digits with the rule res = (res^10 * a^d) mod 1337. The res^10 handles the "shift left by one digit" and a^d adds the new digit's power.

Each step uses modular exponentiation (pow(x, n, MOD) or the helper modpow) so every intermediate value stays small under MOD = 1337 and never overflows.

Example: a = 2, b = [1, 0]. Start res = 1. Digit 1: res = 1^10 * 2^1 = 2. Digit 0: res = 2^10 * 2^0 = 1024. That is 2^10 mod 1337 = 1024, the answer.

It works because folding digit by digit rebuilds the full exponent b exactly, while keeping every number reduced mod 1337.

Time: O(|b|) Space: O(1)