[Leetcode][372. Super Pow] 2 Approaches: BF and Binary Exponentiation

By Long Luo

This article is the solution of Problem 372. Super Pow.

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

Brute Froce

We multiply aa to itself bb times. That is, ab=a×a×a×...×aa^b = a \times a \times a \times ... \times a(b occurrences of a). A simple java implementation of that would be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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(10mbi)O(10^mb_i)mm is the length of array b.
  • Space Complexity: O(1)O(1)

Obiviously, it will over time, so we must find a more efficiently algorithm.

Binary Exponentiation

Recall the 50. Pow(x, n), we develop a fast power algorithm, so we can use it here.

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
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (map.containsKey(nums[i])) {
int idx = map.get(nums[i]);
if (Math.abs(i - idx) <= k) {
return true;
}
map.put(nums[i], i);
} else {
map.put(nums[i], i);
}
}

return false;
}

Analysis

  • Time Complexity: O(i=0m1logbi)O(\sum\limits_{i=0}^{m-1} \log b_i), mm is the length of array bb.
  • Space Complexity: O(1)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. 😉😃💗