[LeetCode][372. Super Pow] 2 Approaches: Brute Force and Binary Exponentiation

By Long Luo

This article is the solution 2 Approaches: Brute Force and Binary Exponentiation of Problem 372. Super Pow.

Intuition

This problem is to find a integer raised to the power a very large number whose length may be $200$ or more.

Brute Froce

We multiply $a$ to itself $b$ times. That is, $a^b = \underbrace{a \times a \dots \times a}_b$.

We can write such code easily.

public static int superPow(int a, int[] b) {
    if (a == 1) {
        return 1;
    }

    int ans = a;
    int len = b.length;
    for (int i = len - 1; i >= 0; i--) {
        int base = (int) Math.pow(10, len - 1 - i);
        int num = b[i] * base;
        for (int j = 1; j < num; j++) {
            ans = ((ans % 1337) * (a % 1337)) % 1337;
        }
    }

    return ans;
}

Analysis

• Time Complexity: $O(10^mb_i)$, $m$ is the length of array b.
• Space Complexity: $O(1)$

Obiviously, it will exceed time limit, so we have to find a more efficiently algorithm.

Binary Exponentiation

Recall the Fast Power Algorithm: Binary Exponentiation, we develop a fast power algorithm, so we can use it here directly.

We didn’t need to change the method of fast power.

public int superPow(int a, int[] b) {
    if (a == 1) {
        return 1;
    }

    int ans = 1;
    int len = b.length;
    for (int i = len - 1; i >= 0; i--) {
        ans = (int) ((long) ans * binaryPower(a, b[i]) % 1337);
        a = binaryPower(a, 10);
    }

    return ans;
}

public static int binaryPower(int base, int exp) {
    int res = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            res = (int) ((long) res * base % 1337);
        }

        base = (int) ((long) base * base % 1337);
        exp = exp >> 1;
    }

    return res;
}

Analysis

• Time Complexity: $O(\sum\limits_{i=0}^{m-1} \log b_i)$, $m$ is the length of array $b$.
• Space Complexity: $O(1)$

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗