Reference: LeetCode
Difficulty: Medium

Problem

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

Note:

  • $-100.0 < x < 100.0$
  • $n$ is a 32-bit signed integer, within the range $[-2^{32}, 2^{32}]$

Example: 

1
2
3
4
5
6
7
8
9
Input: 2.00000, 10
Output: 1024.00000

Input: 2.10000, 3
Output: 9.26100

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Analysis

Brute-Force

Simulate the process, multiply x for n times.

Note:

  • Consider the case n < 0 and n == 0
  • Use long N to handle the case n = -2147483648.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public double myPow(double x, int n) {
  // if (n == 0) return 1.0; // case covered
  long N = n;

  if (N < 0) {
    x = 1 / x;
    N = -N;
  }
  
  double result = 1.0;
  for (long i = 0; i < N; ++i) {
    result *= x;
  }
  
  return result;
}

Time: $O(N)$
Space: $O(1)$

Binary Representation

Since there is $x^{a + b} = x^a \times x^b$, we can process $n$ in binary representation. For example, $x^{52} = x^{110100} = x^{100000} \times x^{010000} \times x^{100}$, so we just need to figure out each of these three terms and calculate the product of them.

  • p starts from $1 (0000001)$ to $32 (1000000)$. Each time we left shift p by one bit.
  • In correspondence with p, we have currProd to store values of $x^{0000001}$, $x^{0000010}$, …, $x^{1000000}$.
  • If the bit is on, we accumulate currProd to result.

Note:

  • Use long N to handle the case n = -2147483648.
  • The condition of while is p <= N.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double myPow(double x, int n) {
  long N = n;
  
  if (N < 0) {
    N = -N; // if not using N, bug case: -2147483648
    x = 1 / x;
  }
  
  double result = 1.0; // product result
  double currProd = x;     // current product init with x^1
  long p = 1;          // p = 000001
  
  while (p <= N) {
    if ((p & N) > 0) { // on
      result *= currProd;  // could be x^{001} / x^{010} / x^{100}
    }
    currProd *= currProd;
    p <<= 1;
  }
  
  return result;
}

Time: $O(\log{N})$ equal to the number of bits required to represent $N$.
Space: $O(1)$

Recursive Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public double myPow(double x, int n) {
  long N = n;

  if (N < 0) {
    N = -N;
    x = 1 / x;
  }

  return helper(N, 1, x);
}

private double helper(long n, long p, double currProd) {
  if (p > n) {
    return 1.0;
  }
  double result = helper(n, p << 1, currProd * currProd);
  if ((p & n) > 0) {
    result *= currProd;
  }
  return result;
}

Time: $O(\log{N})$
Space: $O(\log{N})$