Implement pow(x, n).

123^10 = (123²⁾5
123^5 = 123*(123²⁾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);
    }
}