Problem 39.8 · Math for Coding InterviewsMedium

Super Pow

What it teaches: An exponent given as a digit array: a^(10k + d) = (a^k)^10 × a^d.

Practise it on judges as “Super Pow”.

In plain words

Compute a to a gigantic power, keeping only the remainder after dividing by 1337. The power is given digit by digit. Reading digits left to right, each new digit multiplies the exponent so far by 10 and adds the digit, so the answer becomes (old answer)^10 × a^digit. Taking the remainder after every step keeps numbers small.

Return aᵇ mod 1337. Example: a = 2, b = [1, 0] → 1024.

The problem

Compute aᵇ mod 1337, where b is a huge number given as an array of digits.

Example 1

Input: a = 2, b = [1, 0]
Output: 1024

Constraints

1 ≤ a ≤ 2³¹ − 1
1 ≤ b.length ≤ 2000

Pattern clues in the wording

→ Exponent too big for any integer type

These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int superPow(int a, int[] b) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	a = 2 b = [3]	8
2	a = 2 b = [1,0]	1024
3	a = 1 b = [4,3,3,8,5,2]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Digit-by-digit exponent · O(len × log 10)

Digit-by-digit exponent

Time O(len × log 10) Space O(1)

result = 1; for each digit d: result = pow(result, 10) × pow(a, d) mod 1337.

▶ Dry run: result = result^10 × a^d, digit by digita = 2, b = [1, 0]

vars(vars)

result: 1 (= 2⁰)

Step 1/3Start with result = 1, which is 2 to the power 0.

Approach 1

class Solution {
    private static final int M = 1337;

    public int superPow(int a, int[] b) {
        int result = 1;
        for (int d : b) result = pow(result, 10) * pow(a, d) % M;
        return result;
    }

    private int pow(int base, int e) {
        int r = 1;
        base %= M;
        for (int i = 0; i < e; i++) r = r * base % M;
        return r;
    }
}

Verdict: Horner's rule in the exponent.

Before you submit

Edge cases and common mistakes

Test these inputs

a divisible by 1337 (0)
a = 1

Mistakes people make

Building b as a number (it can have 2000 digits).

Interview

Follow-up questions

Could Euler's theorem shrink the exponent?

Command Palette

The problem

Approaches

Digit-by-digit exponent

Edge cases and common mistakes

Follow-up questions