Implement pow(x, n).
Analysis:
The naive approach is simply to multiply n x's together and get the result. The time complexity is O(n).
Thinking of a better way, when we do linear search with O(n), we optimize the time complexity to O(log(n)) using binary search. In this problem, we can do similar as well.
The following is an example for pow(3, 10), the 'res' is the result that we need to return. We initialize res = 1 so that res = res * x ^ n.
The strategy is to get x as large as possible by squaring it (n>>1 at the same time) so that when we multiple res and x, we have less operations. When n is odd and we couldn't do that, we change res = res*n, so that n = n-1 and n is even again.
Step
|
res
|
x
|
n
|
|---|---|---|---|
| 1 | 1 | 3 | 10 |
| 2 | 1 | 9 | 5 |
| 3 | 9 | 9 | 4 |
| 4 | 9 | 81 | 2 |
| 5 | 9 | 6561 | 1 |
Code:
public class Solution {
public double myPow(double x, int n) {
if (n==0) return 1;
if (x==0 || x==1) return x;
if (n<0) {
x = 1/x;
n = -n;
}
double res = 1;
while (n>0) {
if (n%2==1) {
res *= x;
n--;
} else {
x *= x;
n >>= 1;
}
}
return res;
}
}
Further, we could optimize the above if-else statement inside the while loop such that we are able to skip one operations - from Step 2->Step 4. The code looks like following
public class Solution {
public double myPow(double x, int n) {
if (n==0) return 1;
if (x==0 || x==1) return x;
if (n<0) {
x = 1/x;
n = -n;
}
double res = 1;
while (n>0) {
if (n%2==1) {
res *= x;
}
x *= x;
n >>= 1;
}
return res;
}
}
