50. Pow(x, n) - cocoder39/coco39_LC GitHub Wiki

50. Pow(x, n)

iterative solution

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0 or x == 1:
            return x
        
        if n < 0:
            n *= -1
            x = 1 / x
        
        res = 1 # x^0 = 1
        while n > 0:
            if n % 2 == 1:
                res *= x
                
            if n // 2:
                x *= x
            n //= 2
        return res

2020 Notes:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0 or x == 1:
            return x
        
        if n == 0:
            return 1
        
        if n < 0:
            return 1 / self.myPow(x, -n)
        
        k = n // 2
        tmp = self.myPow(x, k)
        if n % 2 != 0:
            return tmp * tmp * x
        else:
            return tmp * tmp

================================================================

terminal cases are x = 1, n = 0, n = 1. corner cases are n < 0, especially n = INT_MIN may cause overflow

tips:

• if (n % 2), n / 2 = (n - 1) / 2
• x = 1 / x when n < 0, no need to make n = abs(n), which may cause over flow when n = INT_MIN.

double myPow(double x, int n) {
        x = n >= 0 ? x : 1 / x;
        double res = 1;
        while (n) {
            if (n % 2) {
                res *= x;
            }
            x *= x;
            n /= 2;
        }
        return res;
    }

public double myPow(double x, int n) {
        long N = n;
        if (n < 0) {
            x = 1 / x;
            N = -N; // overflow
        }
        return helper(x, N);
    }
    
    private double helper(double x, long n) {
        if (n == 0) {
            return 1;
        }
        
        double half = helper(x, n/2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return x * half * half;
        }
    }

public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N; 
        }
        
        if (N == 0) {
            return 1;
        }
        
        double res1 = 1;
        double res2 = x;
        for (; N > 1; N /= 2) {
            if (N % 2 == 1) {
                res1 *= res2;
            }
            res2 *= res2;
        }
        return res1 * res2;
    }