50. Pow(x, n)

LeetCode

BruteForce

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

Remarks:

  1. TC: $O(|n|)$, SC: $O(1)$.
  2. Takes too long time. Time Limit Exceeded.

Divide and Conquer

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) {
        long N = n;  // use long to avoid overflow when n = Integer.MIN_VALUE
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double result = 1.0;
        while (N > 0) {
            if (N % 2 == 1) result *= x;
            x *= x;
            N /= 2;
        }

        return result;
    }
}

Remarks:

  1. TC: $O(\log N)$, SC: $O(\log N)$

  2. How it works? Consider how we find the binary of a decimal number, by divisions.
    Take pow(2,10) as an example:

    1
    2
    3
    4
    5
    6
    7
    2 | 10   ...0
       -----
     2 | 5   ...1
        ----
      2 | 2  ...0
         ---
          1

    So (10)dec = (1010)bin, which means $10 = 8 + 2 = 2^3 + 2 ^ 1$.

    $2^{10}=2^{2^3}\cdot 2^{2^1}$

    That’s why we only result *= x when N % 2 == 1, as there’s bit 1 in the binary number.