Pow(x, n)

Problem Description

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

Examples

Constraints

• -100.0 < x < 100.0
• -2³¹ ≤ n ≤ 2³¹ - 1
• n is an integer.
• Either x is not zero or n > 0.
• -10⁴ ≤ xⁿ ≤ 10⁴

Binary Exponentiation (Divide and Conquer)

A naive loop multiplying x by itself n times takes O(n) time, which will TLE when n is up to 2³¹.

Instead, we can use binary exponentiation:

• If n is even, xⁿ = (x * x)^(n / 2)
• If n is odd, xⁿ = x * (x * x)^((n - 1) / 2)

This divides n by 2 at each step, reducing complexity to O(log n).

To handle negative values of n:

• x⁻ⁿ = (1 / x)ⁿ
• Overflow check: if n = -2³¹ (integer minimum value), changing it to positive would overflow a standard 32-bit signed integer. We must convert n to a 64-bit integer type first before negating.

Solution: Binary Exponentiation (Iterative)

class Solution {
    public double myPow(double x, int n) {
        long N = n; // convert to long to prevent overflow when negating INT_MIN
        if (N < 0) {
            x = 1.0 / x;
            N = -N;
        }

        double result = 1.0;
        double currentProduct = x;

        while (N > 0) {
            if (N % 2 == 1) {
                result *= currentProduct;
            }
            currentProduct *= currentProduct;
            N /= 2;
        }

        return result;
    }
}

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1.0 / x
            n = -n

        result = 1.0
        current_product = x

        while n > 0:
            if n % 2 == 1:
                result *= current_product
            current_product *= current_product
            n //= 2

        return result

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1.0 / x;
            N = -N;
        }

        double result = 1.0;
        double currentProduct = x;

        while (N > 0) {
            if (N % 2 == 1) {
                result *= currentProduct;
            }
            currentProduct *= currentProduct;
            N /= 2;
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(log N) where N is the power parameter n.
• Space Complexity: O(1).

← All Problems