# LeetCode 372: Super Pow

## Problem Restatement

We are given:

| Variable | Meaning |
|---|---|
| `a` | Positive integer base |
| `b` | Very large exponent represented as an array of digits |

We need to compute:

```python
a^b mod 1337
```

The exponent can be extremely large, so we cannot convert the entire digit array into a normal integer directly.

The problem statement defines:

```python
b = [1, 2, 3]
```

as the exponent:

```python
123
```

The modulus is always:

```python
1337
```

The official examples include:

```python
a = 2
b = [3]
```

with answer:

```python
8
```

and:

```python
a = 2
b = [1, 0]
```

with answer:

```python
1024
```

modulo `1337`. ([leetcode.com](https://leetcode.com/problems/super-pow/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `a` and digit array `b` |
| Output | `a^b mod 1337` |
| Exponent format | Decimal digits in array form |
| Modulus | Always `1337` |

Example function shape:

```python
def superPow(a: int, b: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
a = 2
b = [3]
```

This means:

```python
2^3 = 8
```

Then:

```python
8 mod 1337 = 8
```

So the answer is:

```python
8
```

Example 2:

```python
a = 2
b = [1, 0]
```

This means:

```python
2^10 = 1024
```

Then:

```python
1024 mod 1337 = 1024
```

So the answer is:

```python
1024
```

Example 3:

```python
a = 1
b = [4, 3, 3, 8, 5, 2]
```

Since:

```python
1^anything = 1
```

the answer is:

```python
1
```

## First Thought: Build the Exponent

A direct idea is:

1. Convert the digit array into a large integer.
2. Compute:

```python
pow(a, exponent, 1337)
```

Example:

```python
b = [1, 2, 3]
```

becomes:

```python
123
```

This works in Python because Python integers are arbitrary precision.

But the problem is designed to test modular exponentiation ideas rather than relying on huge integers.

We should solve it using exponent decomposition.

## Key Insight

Suppose the exponent digits are:

```python
b = [1, 2, 3]
```

Then:

```python
123 = 12 * 10 + 3
```

So:

```python
a^123 = a^(12 * 10 + 3)
```

Using exponent rules:

```python
a^(x + y) = a^x * a^y
```

and:

```python
a^(10x) = (a^x)^10
```

we get:

```python
a^123 = (a^12)^10 * a^3
```

This creates a recursive structure.

If we remove the last digit `d` from the exponent:

```python
remaining = previous digits
```

then:

```python
a^(remaining * 10 + d)
=
(a^remaining)^10 * a^d
```

All computations are done modulo `1337`.

## Modular Arithmetic Rule

We repeatedly use:

```python
(x * y) mod m
=
((x mod m) * (y mod m)) mod m
```

This keeps numbers small.

## Algorithm

Define:

```python
MOD = 1337
```

Recursive process:

1. If `b` is empty:
   - Return `1`.
2. Remove the last digit `d`.
3. Recursively compute:

```python
part1 = superPow(a, remaining_digits)
```

4. Compute:

```python
part1^10 mod MOD
```

5. Compute:

```python
a^d mod MOD
```

6. Multiply both modulo `MOD`.

Use fast modular exponentiation for powers.

## Correctness

Suppose the exponent represented by `b` is:

```python
E = 10Q + d
```

where:

| Variable | Meaning |
|---|---|
| `Q` | Exponent formed by all digits except the last |
| `d` | Last digit |

Then:

```python
a^E
=
a^(10Q + d)
=
(a^Q)^10 * a^d
```

The recursive call computes:

```python
a^Q mod 1337
```

Raising it to the 10th power and multiplying by:

```python
a^d mod 1337
```

produces:

```python
a^E mod 1337
```

because modular multiplication preserves correctness.

The recursion eventually reaches the empty exponent, which represents exponent `0`. Since:

```python
a^0 = 1
```

the base case is correct.

Therefore, the algorithm correctly computes:

```python
a^b mod 1337
```

for every valid input.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Number of digits in `b` |

Each recursion level processes one digit.

Fast exponentiation uses logarithmic time in the exponent.

But the only exponents used are:

```python
10
```

and:

```python
0 through 9
```

which are constant-size.

So:

| Metric | Value |
|---|---:|
| Time | `O(n)` |
| Space | `O(n)` recursion stack |

## Implementation

```python
class Solution:
    MOD = 1337

    def superPow(self, a: int, b: list[int]) -> int:
        if not b:
            return 1

        last_digit = b.pop()

        part1 = self._mod_pow(
            self.superPow(a, b),
            10,
        )

        part2 = self._mod_pow(a, last_digit)

        return (part1 * part2) % self.MOD

    def _mod_pow(self, base: int, exponent: int) -> int:
        result = 1
        base %= self.MOD

        while exponent > 0:
            if exponent & 1:
                result = (result * base) % self.MOD

            base = (base * base) % self.MOD
            exponent >>= 1

        return result
```

## Code Explanation

The modulus is fixed:

```python
MOD = 1337
```

The base case handles exponent `0`:

```python
if not b:
    return 1
```

We remove the last exponent digit:

```python
last_digit = b.pop()
```

Suppose:

```python
b = [1, 2, 3]
```

Then:

| Part | Meaning |
|---|---|
| Remaining digits | `12` |
| Last digit | `3` |

The recursive call computes:

```python
a^12 mod 1337
```

Then:

```python
part1 = (a^12)^10 mod 1337
```

and:

```python
part2 = a^3 mod 1337
```

Finally:

```python
(part1 * part2) % MOD
```

gives:

```python
a^123 mod 1337
```

The helper `_mod_pow` uses fast exponentiation.

Instead of multiplying `base` repeatedly, it squares the base and halves the exponent:

```python
base = (base * base) % MOD
exponent >>= 1
```

This gives logarithmic exponentiation time.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.superPow(2, [3]) == 8

    assert s.superPow(2, [1, 0]) == 1024

    assert s.superPow(1, [4, 3, 3, 8, 5, 2]) == 1

    assert s.superPow(2, [1, 2, 3]) == pow(2, 123, 1337)

    assert s.superPow(2147483647, [2, 0, 0]) == pow(2147483647, 200, 1337)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `2^[3]` | Small exponent |
| `2^[1,0]` | Multi-digit exponent |
| `1^anything` | Multiplicative identity |
| `2^[1,2,3]` | Recursive exponent decomposition |
| Large base | Confirms modular reduction works |