# x to the n

MathBinary SearchD&C

## # Solution

Calculate pow(a,n), or $a^n$. Could do in both recursion and iteration.

### # Recursion

Complexity

time: $O(\log n)$
space: $O(\log n)$

The following solution actually TLS b/c of highlighted lines, specifically on the following test case:

x = 0.00001
n = 2147483647

1
2

def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1.0
elif n < 0:
return 1 / self.myPow(x, -n)
elif n % 2:
return self.myPow(x, n//2) * self.myPow(x, n//2) * x
return self.myPow(x, n//2) * self.myPow(x, n//2)

1
2
3
4
5
6
7
8

Works after combining duplicate myPow calls:

def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
elif n < 0:
return 1 / self.myPow(x, -n)
elif n % 2:
return x * self.myPow(x, n-1)
return self.myPow(x*x, n//2)

1
2
3
4
5
6
7
8

Or could store the common half:

def myPow(self, a, b):
if b == 0:
return 1
if b < 0:
return 1.0 / self.myPow(a, -b)
half = self.myPow(a, b // 2)
if b % 2 == 0:
return half * half
else:
return half * half * a

1
2
3
4
5
6
7
8
9
10

### # Iteration

Complexity

time: $O(\log n)$
space: $O(1)$

def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
elif n < 0:
n = -n
x = 1/x
res = 1
prod = x
is_pos = n > 0
while n > 0:
if n % 2:
res = prod * res
prod *= prod
n //= 2
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

In this similar LintCode problem (opens new window), the modular arithmetic is now added. That is, calculate pow(a,n,b), or $a^n \mod b$.

The corresponding complexities of recursion or iteration are the same.

### # Recursion

Highlighted lines fix the n == 0, b == 1 case such as 3**0 % 1:

def fastPower(self, a, b, n):
if b == 1:
return 0
if n == 0:
return 1
# last 4 lines could also be:
# if n == 0:
#     return 1 % b
if n % 2:
return a * self.fastPower(a, b, n-1) % b
return self.fastPower(a, b, n//2)**2 % b

1
2
3
4
5
6
7
8
9
10
11

### # Iteration

def fastPower(self, a, b, n):
if b == 1:
return 0
res = 1
while n > 0:
if n % 2:
res = res * a % b
n -= 1
else:
a = a * a % b
n //= 2
return res % b

1
2
3
4
5
6
7
8
9
10
11
12