Implement pow(x, n).
123^10 = (1232)5
123^5 = 123*(1232)2
time complexity O(logn) if multiply operation is O(1)
// iterative
// Time O(logn)
public class Solution {
public double myPow(double x, int n) {
if(n == 0) {
return 1;
}
if(n < 0) {
n = -n;
x = 1 / x;
}
double result = 1;
while(n > 0){
//n is odd
if(n & 1) {
result *= x;
}
x *= x;
n >>= 1;
}
return result;
}
}
// recursion
// time log(n)
public class Solution {
public double pow(double x, int n) {
if(n == 0)
return 1;
if(n<0){
n = -n;
x = 1/x;
}
return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
}
}
