source: https://leetcode.com/problems/powx-n/
C/C++ Solution to LeetCode problem 50. Pow(x, n).
Problem
Implement pow(x, n)
, which calculates x
raised to the power n
(i.e., xn
).
Examples
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints
-100.0 < x < 100.0
-231 <= n <= 231-1
n
is an integer.-104 <= xn <= 104
Solution
Instead of multiplying by x
n-times
we will optimize (reduce the amount of times we multiply) using the right-shift bitwise operation.
- We initialize our
result = 1
. - While
n > 0
(we use the absolute value of n). - If the last (LSB) of
n
is1
we multiplyresult * x
. - We multiply
x
by itself (x * x
). - And
right-shift
n
(n >> 1
). - Finally, if the original
n<0
, then the result will be1/result
otherwiseresult
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
double myPow(double x, int n) {
double ans = 1.0;
bool neg = n < 0;
n = abs(n);
while (n > 0) {
if (n & 1)
ans = ans * x;
x = x * x;
n = n >> 1;
}
return neg ? 1 / ans: ans;
}
};