50. Pow(x, n)

發表於 | 分類於

problem

solution

option 1 - recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    double myPow(double x, int n) {
        if(n==0 || x==1) return 1;
        if(n==1) return pow(x,1);
        // avoid overflow
        if(n<0) return 1/(x*myPow(x,-(n+1)));
        else {
            // avoid time limit
            if(n%2==1) return x*myPow(x,n-1);
            else{
                double half = myPow(x,n/2);
                return half*half;
            }
        }
        
    }
};

option 2 - iterative

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    double myPow(double x, int n) {
        if(x==1 || n==0) return 1;
        double ret= 1.0;
        for(int i=n;i!=0;i/=2){
            if(i%2!=0) ret*= x;
            x*=x;
        }
        return n<0?1/ret:ret;
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(1)