50. Pow(x, n)

problem description

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0

• n is a 32-bit signed integer, within the range [−231, 231 − 1]

algorithm thought

求2的100次方，如果直接乘100次，其实没有必要。完全可以求4的50次方，然后16的25次方。这样每次能减少一半的计算量。这里的问题就是还有负数。如果是负数的话，首先将x化为1/x。然后将n转化为正数。最后，一种最特殊的情况就是如果数字是INT_MIN,最后直接将n-1即可。这样INT_MIN就会变INT_MAX

code

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n<0){
            x=1/x;
            if(n==INT_MIN){
                return x*myPow(x,(n-1));
            }
            n=-n;
        }
        return n%2?x*myPow(x*x,n/2):myPow(x*x,n/2);
    } 
};

algorithm analysis

每次将次数降低一半，时间复杂度O(lgn)