50. Pow(x, n)
https://leetcode.com/problems/powx-n/
Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10 Output: 1024.00000
Example 2:
Input: 2.10000, 3 Output: 9.26100
Example 3:
Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
- -100.0 < x < 100.0
- n is a 32-bit signed integer, within the range [−231, 231 − 1]
---
Intuition
if pow < 0
pow = Math.abs(pow)
base = 1.0 / base
Cast power to long to prevent against integer overflow when taking Math.abs
while (pow > 0) {
pow = pow / 2;
}
Above is log N complexity
To compute power, square the number in every iteration - running calculation
If power is odd, multiply answer with number one extra time
---
Time - O(log N)
Space - O(1)
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public double myPow(double x, int n) { | |
| // protect against int overflow / underflow | |
| long power = n; | |
| if (power < 0) { | |
| power = Math.abs(power); | |
| x = 1.0 / x; | |
| } | |
| double ans = 1.0; | |
| // square the current num, while power > 0 => O(log n) time | |
| while (power > 0) { | |
| if (power % 2 == 1) { | |
| ans *= x; | |
| } | |
| x *= x; | |
| power = power / 2; | |
| } | |
| return ans; | |
| } | |
| } |
