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})$


Comment