-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0050 [M] Pow(x, n)
Code with Senpai edited this page Sep 14, 2022
·
36 revisions
3 cases
(0 -> 1)
- negative =
1/x^-n
2^-2 = 1/2^2 = 1/4 = 0.25
A = x^n/2 (half)
A * A (whole)
- positive even (n) =
whole
A * A = x^n
4^2 = 4^2/2 * 4^2/2 = 4 * 4
- positive odd (n-1) =
whole * x
A * A * x = x^(n-1) * x = x^n
4^1 = 4^0/2 * 4^0/2 * 4 = 1 * 1 * 4
understand and memorize (0,0) (0,1) (1,1)
2^2 * 2^2 = 2^4
x = 2
x^2 = 4
n = 2
x^(2*n) = x^4 = 16 : we do not have to multiply x by another n times
(x^n)^2 = 4^2 = 16 : we can multiply by the c times for less operations
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0: # 0
return 1
elif n < 0: # negative
return self.myPow(1 / x, -n)
elif n > 0: # positive
half = self.myPow(x, n // 2)
whole = half * half
if n % 2 == 0: # even
return whole
else: # odd
return whole * x
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0: return 1
if n < 0:
# n is negative
return self.myPow(1/x, -n) # 1/x^(-n)
else:
# n is positive
x_ndiv2 = self.myPow(x, n // 2) # x^(n/2)
if n % 2 == 0:
# n is even: x^n
x_n = x_ndiv2 * x_ndiv2
else:
# n is odd: x^(n-1) * x = x^n
x_nmin1 = x_ndiv2 * x_ndiv2
x_n = x_nmin1 * x
return x_n
footer