50. Pow(x, n)

Posted on | Edited on | Views:

LeetCode

Approach 1: Brute Force, Time complexity: O(n), Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public double myPow(double x, int n) {
        // n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]
        // long type because: -2^31 -> 2^31, overflow issue occurs
        long N=n;
        if(N<0){
            x=1/x;
            N=-N;
        }
        double ans=1;
        for(long i=0;i<N;i++) ans*=x;
        return ans;
    }
}

Approach 2: Fast Power Algorithm Recursive, Time complexity: O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    private double fastPow(double x,long n){
        if(n==0) return 1.0;
        double half=fastPow(x, n/2);
        if(n%2==0) return half*half;
        else return half*half*x;
    }
    public double myPow(double x, int n) {
        long N=n;
        if(N<0){
            x=1/x;
            N=-N;
        }
        return fastPow(x,N);
    }
}

Approach 3: Fast Power Algorithm Iterative, Time complexity: O(logn), Space complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double myPow(double x, int n) {
        long N=n;
        if(N<0){
            x=1/x;
            N=-N;
        }
        double ans=1,currProduct=x;
        for(long i=N;i>0;i/=2){
            if(i%2==1) ans*=currProduct;
            currProduct*=currProduct;
        }
        return ans;
    }
}

0%