Pow(x, n)

How it works

We want to compute ( x^n ) efficiently, even when n is very large (positive or negative).

The brute force approach multiplies x repeatedly and takes O(n) time, which is too slow. Instead, we use binary exponentiation, which reduces the time complexity to O(log n).

The key ideas are:

• Any number n can be written in binary
• If the current power is odd, we must include one extra x in the result
• We repeatedly:
  • square the base (x = x * x)
  • halve the exponent (power = power // 2)

For negative powers:

• ( x^n = \frac{1}{x^{|n|}} )
• so we compute using abs(n) and take the reciprocal at the end if needed

This iterative version avoids recursion and works efficiently with constant extra space.

Steps

1. Handle edge cases:
   • If x == 0, return 0
   • If n == 0, return 1
2. Initialize:
   • res = 1 (stores the final answer)
   • power = abs(n) (work with positive exponent)
3. While power > 0:
   • If power is odd:
     • multiply res by x
   • Square the base:
     • x = x * x
   • Divide the exponent by 2:
     • power = power >> 1
4. If n is negative:
   • return 1 / res
5. Otherwise:
   • return res

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Integer Overflow When Negating n

When n is Integer.MIN_VALUE (-2147483648), computing abs(n) or -n overflows because the positive equivalent exceeds Integer.MAX_VALUE. Always cast to a long before taking the absolute value to avoid this undefined behavior.

In JavaScript, Math.abs(n) is safe on its own (numbers are doubles), but the bitwise operators are not: power & 1 and power >>= 1 first convert power to a signed 32-bit integer, so 2147483648 becomes -2147483648 and the loop terminates immediately. Use power % 2 and Math.floor(power / 2) instead of bitwise operations.

Forgetting to Handle Negative Exponents

A negative exponent means the result is 1 / x^|n|. Omitting this reciprocal step returns the wrong answer for all negative n values. Compute the power using the absolute value, then invert if n was negative.

Using Brute Force for Large Exponents

Multiplying x by itself n times works but times out for large n (e.g., n = 2^31 - 1). Binary exponentiation reduces the number of operations from O(n) to O(log n) by squaring the base and halving the exponent at each step.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        if n == 0:
            return 1

        res = 1
        power = abs(n)

        while power:
            if power & 1:
                res *= x
            x *= x
            power >>= 1

        return res if n >= 0 else 1 / res

class Solution {
public:
    double myPow(double x, int n) {
        if (x == 0) return 0;
        if (n == 0) return 1;

        double res = 1;
        long power = abs((long)n);

        while (power) {
            if (power & 1) {
                res *= x;
            }
            x *= x;
            power >>= 1;
        }

        return n >= 0 ? res : 1 / res;
    }
};