LC #50 - Pow(x, N)

**Pow(x, n)**

Description

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

Example

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

Example 2:
Input: 2.10000, 3
Output: 9.26100

Example 3:
Input: 2.00000, -2
Output: 0.25000

Solution

The basic thought of this problem is Divide & Conquer. We can divide it into two halves and then calculate it. For example1 n = 10, then we can have 210 = 25 * 25, next we calculate 22 and 23, but wait a second, when n is odd, we need to calculat twice, why can’t we just calculate 22, and then 22 * 22 * 2, so based on this, we can come up with the following algorithm. This is just for x >= 0, if x < 0, we need to pay a little more attention.

Algorithm

My algorithm

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def myPow(self, x, n):
if n == 0:
return 1
if n == 1:
return x
if n == -1:
return 1 / x

if n > 0:
sign = 1
else:
sign = -1
left = self.myPow(x, sign * (abs(n) // 2)) # the reason why I write in this way is because -3 // 2 = -2 in python, but I need it to be -1

if not n % 2: # when n is even
right = left
elif n > 0 and n % 2: # when n is odd and n > 0
right = left * x
elif n < 0 and n % 2: # when n is odd and n < 0
right left / x
return left * right

This is my algorithm, a little long, but the basic idea is correct. Let’s see a more concise one.

Concise algorithm

Python

1
2
3
4
5
6
7
8
9
def myPow(self, x, n):
if n == 0:
return 1

if n < 0:
return 1 / self.myPow(x, -n)
if n % 2:
return x * self.myPow(x, n - 1)
return self.myPow(x * x, n // 2)

This one is really elegant and concise…

Complexity

Time Complexity: O(log(n)).
Space Complexity: O(1).

0%