# x to the n

## # 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


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)


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)


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


### # 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


## # Follow Up

In this similar LintCode problem, 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


### # 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

Last Updated: 7/19/2020, 3:45:14 PM