Problem #50: Pow(x, n)

Intuition & Strategy Breakdown

Use binary exponentiation (Fast Power). Recursively compute pow(x, n // 2), squaring the result and multiplying by x if n is odd, achieving O(log N) time complexity.

Python Solution

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

Java Solution

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double res = 1;
        while (N > 0) {
            if (N % 2 == 1) {
                res *= x;
            }
            x *= x;
            N /= 2;
        }
        return res;
    }
}