Pow(x, n)

Implement pow(x, n), which returns x raised to the integer power n. This is LeetCode 50. The limits are -100.0 < x < 100.0 and -2^31 <= n <= 2^31 - 1. Either x is not zero or n > 0, and the result lies between -10^4 and 10^4.

The outputs below are written with five decimals, the way LeetCode prints them.

Example 1
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1 / 2^2 = 1 / 4.

How to Think About It

Step 1: Multiply n times

The obvious loop multiplies x into a result |n| times. With n up to about 2.1 × 10^9, a single call would need billions of multiplications, so it is far too slow.

Step 2: Halve the exponent

Squaring doubles the exponent: x^10 = (x^2)^5. When the exponent is odd, set one factor aside first: x^5 = x × x^4. Each step halves the exponent, so only about log2(n) steps are needed, at most 32 for any int.

Step 3: Read the steps from the binary form

Write 10 in binary as 1010, which means 10 = 8 + 2. So x^10 = x^8 × x^2. Keep squaring x to get x^1, x^2, x^4, x^8, ..., and multiply the result by the powers whose bit is 1. This loop version is exponentiation by squaring, also called fast or binary exponentiation.

Step 4: Negative exponents and the one value that breaks

x^-n = (1/x)^n, so a negative exponent becomes a positive one with 1/x as the base. The trap is n = Integer.MIN_VALUE, which is -2147483648. Its negation, 2147483648, does not fit in an int, so -n wraps back to -2147483648.

Copying n into a long before negating avoids that, since a long holds 2147483648 easily. Divide Two Integers has the same Integer.MIN_VALUE edge and the same doubling idea.

Walkthrough

Example 1: x = 2, n = 10 (binary 1010). Each row is one pass of the loop; x is squared at the end of every pass.

PasspowerLowest bitx at startresult afterpower after shift
1100215
251442
3201641
41125610240

The two 1 bits picked up 4 = 2^2 and 256 = 2^8, and 4 × 256 = 1024. Four passes replaced ten multiplications.

Java Solution

The method turns a negative exponent into a positive one, then walks the bits of the exponent from lowest to highest, squaring the base at each step.

  • The long copy: long power = n widens before negating, so -power is 2147483648 when n is Integer.MIN_VALUE. myPow(2.0, Integer.MIN_VALUE) returns 0.0, because 2^-2147483648 is far below the smallest double.
  • The odd bit: (power & 1) == 1 tests the lowest bit. When it is set, the current square of x is part of the answer and goes into result.
  • Shifting: power >>= 1 drops the bit just used, and x *= x moves the base to the next power of two, so the two stay in step.
  • Small cases: n = 0 skips the loop and returns 1.0. A negative base keeps its sign for odd exponents: myPow(-2.0, 3) is -8.0 and myPow(-1.0, Integer.MAX_VALUE) is -1.0.

A common mistake is to negate the int itself with n = -n, or to use Math.abs(n). Both leave Integer.MIN_VALUE negative, the loop never runs, and myPow(2.0, Integer.MIN_VALUE) returns 1.0 instead of 0.0.

Java
public class PowXN {
    public double myPow(double x, int n) {
        long power = n;                // long, so -Integer.MIN_VALUE does not overflow
        if (power < 0) {
            x = 1 / x;
            power = -power;
        }
        double result = 1.0;
        while (power > 0) {
            if ((power & 1) == 1) {    // this bit of the exponent is set
                result *= x;
            }
            x *= x;                    // x^1, x^2, x^4, x^8, ...
            power >>= 1;
        }
        return result;
    }
}

Complexity

  • Time: O(log |n|). Each pass of the loop halves power, so the loop runs once per binary digit of |n|, at most 32 times even for Integer.MIN_VALUE.
  • Space: O(1). The loop keeps only power, result and the squared base, and unlike a recursive version it uses no call stack.

Each squaring roughly doubles the relative rounding error. For exponents up to 10^5, results stayed within 10^-11 of Math.pow in relative terms. For exponents near 2^31 they can differ from about the 7th significant digit, so compare doubles with a tolerance. A related check on powers is Power of Three.