[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 or more.
Brute Froce
We multiply to itself times. That is, .
We can write such code easily.
1 | public static int superPow(int a, int[] b) { |
Analysis
- Time Complexity: , is the length of array b.
- Space Complexity:
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 | public int superPow(int a, int[] b) { |
Analysis
- Time Complexity: , is the length of array .
- Space Complexity:
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. 😉😃💗