[LeetCode] 50. Pow(x, n)

Posted on | In

Problem

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

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
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 [$−2^{31}$, $2^{31} − 1$]

Explanation

  1. Let’s see an example first, $2^4 = 4^2 = 16^1$.

  2. We can divide the power by 2 and multiple the base by itself until power is 1.

  3. Default the res equal 1, if the power is an odd number, we can multiple the res by base, then power subtract 1 to become even.

  4. If power is a negative number, we can revert power to positive then after we get the final res, we use 1 to divide the res.

  5. The corner case is the minimum of integer is -2147483648 and the maximum of integer is 2147483647, which is 1 less than the revert of minimum integer. In order to fix it, before we revert the negative power, we add 1 to it, and res multiple by the base because $-2147483648 + 1 = -2147483647$, when we revert it can be a maximum integer now, but we multiple the base one time less, so that is why we multiple the res by base.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public double myPow(double x, int n) {
        if (x == 1 || n == 0) return 1;
        if (n == 1) return x;
        if (n < 0) {
            return 1 / (x*myPow(x, -1*(n+1)));
        }
        double res = 1;
        while(n > 1) {
            if (n % 2 == 1) {
                res *= x;
                n -= 1;
            }
            n = n/2;
            x = x*x;
        }
        return res*x;
    }
}