Thursday, August 13, 2015

[LeetCode] Pow(x, n)

Problem Statement (link):
Implement pow(xn).

Analysis:
The naive approach is simply to multiply n x's together and get the result. The time complexity is O(n).

Thinking of a better way, when we do linear search with O(n), we optimize the time complexity to O(log(n)) using binary search. In this problem, we can do similar as well.

The following is an example for pow(3, 10), the 'res' is the result that we need to return. We initialize res = 1 so that res = res * x ^ n.
The strategy is to get x as large as possible by squaring it (n>>1 at the same time) so that when we multiple res and x, we have less operations. When n is odd and we couldn't do that, we change res = res*n, so that n = n-1 and n is even again.

Step
res
x
n
11310
2195
3994
49812
5965611

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n==0) return 1;
        if (x==0 || x==1) return x;
        if (n<0) {
            x = 1/x;
            n = -n;
        }
        double res = 1;
        while (n>0) {
            if (n%2==1) {
                res *= x;
                n--;
            } else {
                x *= x;
                n >>= 1;
            }
        }
        return res;
    }
}

Further, we could optimize the above if-else statement inside the while loop such that we are able to skip one operations - from Step 2->Step 4. The code looks like following

public class Solution {
    public double myPow(double x, int n) {
        if (n==0) return 1;
        if (x==0 || x==1) return x;
        if (n<0) {
            x = 1/x;
            n = -n;
        }
        double res = 1;
        while (n>0) {
            if (n%2==1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}


No comments:

Post a Comment