[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.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public 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.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28public 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. 😉😃💗