2014年4月14日 星期一

[LeetCode] Pow(x, n)

Problem:
Implement pow(xn).
Solution:O(log n)
public class Solution {
    public double pow(double x, int n) {
        if(n == 0)
            return 1.0;
        int flag = 1;
        if(x < 0 &&  (n%2 == 1))
            flag = -1;
        
        x = Math.abs(x);
        if(x == 1.0)
            return x*flag;
            
        if(n<0)
            return 1/pow(x, -n);
        
        double ret = 1.0;
        double q = x;
        while(n>0){
            if(n%2 == 1)
                ret*=q;
            q*=q;
            n/=2;
        }
        
        return ret*flag;
    }
}
Key Concept: Except special case, using previous binary result

沒有留言:

張貼留言