Pow(x, n)

Medium Problem 150 of 151 Java and Python

Practice on LeetCode

Problem

Implement pow(x, n), which calculates x raised to the power n (xⁿ). n may be negative.

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
Why: 2⁻² = 1/4.

Constraints

-100.0 < x < 100.0
-2³¹ ≤ n ≤ 2³¹ – 1

Explanation

Multiplying x by itself n times is too slow for n near 2³¹. Instead use xⁿ = (x²)^(n/2), with one extra factor of x when n is odd. Each step halves n, so it takes about log₂ n steps.

For a negative n, compute (1/x)^(-n). In Java, store n in a long first: -(-2³¹) does not fit in an int.

Approach 1 · Naive

Multiply n times

Time O(|n|)
Space O(1)

Multiply x into the result |n| times, then invert for negative n.

Repeat |n| times: result *= x.
If n < 0, return 1 / result.

Java

class Solution {
    public double myPow(double x, int n) {
        long count = Math.abs((long) n);
        double result = 1;
        for (long i = 0; i < count; i++) {
            result *= x;
        }
        return n < 0 ? 1 / result : result;
    }
}

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        result = 1.0
        for _ in range(abs(n)):
            result *= x
        return 1 / result if n < 0 else result

Approach 2 · Optimal

Exponentiation by squaring

Time O(log |n|)
Space O(1)

Walk the bits of n: when the current bit is 1, multiply the result by the current power of x; square that power every step.

Use N = n as a 64-bit number; if N < 0, set x = 1/x, N = -N.
While N > 0: if N is odd, result *= x; then x *= x, N /= 2.
Return result.

Java

class Solution {
    public double myPow(double x, int n) {
        long power = n;
        if (power < 0) {
            x = 1 / x;
            power = -power;
        }
        double result = 1;
        while (power > 0) {
            if ((power & 1) == 1) {
                result *= x;
            }
            x *= x;
            power >>= 1;
        }
        return result;
    }
}

Python

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

Complexity compared

Approach	Time	Space
Naive Multiply n times	O(\|n\|)	O(1)
Optimal Exponentiation by squaring	O(log \|n\|)	O(1)

Key takeaways

Fast exponentiation also powers modular arithmetic (a^b mod m) and matrix powers for Fibonacci in O(log n).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem