LC 0050 [M] Pow(x, n) - ALawliet/algorithms GitHub Wiki

3 cases

(0 -> 1)

1. negative = 1/x^-n 2^-2 = 1/2^2 = 1/4 = 0.25

A = x^n/2 (half)
A * A (whole)

2. positive even (n) = whole

A * A = x^n
4^2 = 4^2/2 * 4^2/2 = 4 * 4

3. 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