141.Pow(x, n)

MediumMath & Geometry · 6/8

Problem

Implement pow(x, n), which computes x raised to the integer power n (that is, x^n).

n may be negative (meaning 1 / x^|n|) and can be as small as -2^31. Do not use Math.pow.

Examples

Input:  x = 2.00000, n = 10
Output: 1024.00000

Input:  x = 2.10000, n = 3
Output: 9.26100

Input:  x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1 / 2^2 = 1/4 = 0.25.

Constraints

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n is an integer.
Either x is not zero or n > 0.
-10^4 <= x^n <= 10^4

💡 Key Insight

Exponentiation by squaring: x^n = (x^(n/2))² when n is even and x · (x^(n/2))² when odd. Each step halves the exponent, so only O(log n) multiplications are needed instead of n. Handle a negative exponent by computing with 1/x and |n| — but store |n| in a long, because -(-2^31) overflows an int.

Brute Force (Repeated Multiplication)

TimeO(|n|)SpaceO(1).

Intuition

Multiply x by itself |n| times, then invert if n was negative. Correct, but n can be about two billion, which is far too slow (LeetCode times out).

Algorithm

N = |n| as a long; if n < 0, set x = 1 / x.
result = 1; repeat N times: result *= x.
Return result.

Visualization

x = 2, n = 10
result: 1 → 2 → 4 → 8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024   (10 multiplications)

Code

java

class Solution {
    public double myPow(double x, int n) {
        long N = n;            // long: -(-2^31) does not fit in an int
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double result = 1.0;
        for (long i = 0; i < N; i++) {
            result *= x;       // one multiplication per unit of exponent
        }
        return result;
    }
}

Complexity

Time: O(|n|) — up to about 2 · 10^9 multiplications; too slow.
Space: O(1).

Recursive Fast Power

TimeO(log n)SpaceO(log n)

Intuition

Compute half = x^(N/2) once and square it. If N is odd, multiply by one extra x. The exponent halves at each level, so recursion depth is about log₂ N ≈ 31.

Algorithm

Convert to long N; if negative, invert x and negate N.
fastPow(x, N):
- If N == 0, return 1.
- half = fastPow(x, N / 2).
- Return half * half if N is even, otherwise half * half * x.

Visualization

flowchart TD
    A["pow(2, 10)"] --> B["pow(2, 5)"]
    B --> C["pow(2, 2)"]
    C --> D["pow(2, 1)"]
    D --> E["pow(2, 0) = 1"]
    E -.->|"1·1·2"| D2["pow(2,1) = 2"]
    D2 -.->|"2·2"| C2["pow(2,2) = 4"]
    C2 -.->|"4·4·2"| B2["pow(2,5) = 32"]
    B2 -.->|"32·32"| A2["pow(2,10) = 1024"]

Code

java

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

    private double fastPow(double x, long n) {
        if (n == 0) return 1.0;
        double half = fastPow(x, n / 2); // computed once, reused twice
        return (n % 2 == 0) ? half * half : half * half * x;
    }
}

Complexity

Time: O(log n) — the exponent halves every call.
Space: O(log n) — recursion depth (at most ~32 frames).

Iterative Binary ExponentiationOptimal

TimeO(log n)SpaceO(1).

Intuition

Write N in binary: 10 = 1010₂, so x^10 = x^8 · x^2. Keep a running base that takes the values x, x², x⁴, x⁸, ... by squaring, and multiply it into result whenever the current low bit of N is 1. Same O(log n) work, no recursion.

Algorithm

Convert to long N; if negative, invert x and negate N.
result = 1, base = x.
While N > 0:
- If N is odd (N & 1), result *= base.
- base *= base; N >>= 1.
Return result.

Visualization

x = 2, n = 10 (binary 1010)

N (bin)  low bit  base       result
1010     0        2          1
101      1        4          4        (result *= 4)
10       0        16         4
1        1        256        1024     (result *= 256)
0        -        -          return 1024

Code

java

class Solution {
    public double myPow(double x, int n) {
        long N = n;              // avoid overflow when n == Integer.MIN_VALUE
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double result = 1.0;
        double base = x;         // x^(2^k) at step k
        while (N > 0) {
            if ((N & 1) == 1) {
                result *= base;  // this bit contributes base
            }
            base *= base;
            N >>= 1;
        }
        return result;
    }
}

Complexity

Time: O(log n) — one iteration per bit of |n| (at most 32).
Space: O(1).

Complexity Comparison

Approach	Time	Space
Repeated Multiplication	O(n)	O(1)
Recursive Fast Power	O(log n)	O(log n)
Iterative Binary Exponentiation	O(log n)	O(1)

Common Pitfalls

Negating n as an int — -Integer.MIN_VALUE is still Integer.MIN_VALUE, so the exponent stays negative. Use a long.
Calling fastPow(x, n / 2) twice instead of storing it in half — that is back to O(n) time.
Forgetting the odd case (half * half * x).
Inverting the final result instead of x is fine too, but don't do both.