50. Pow(x, n) - Explanation

Description

Pow(x, n) is a mathematical function to calculate the value of x raised to the power of n (i.e., x^n).

Given a floating-point value x and an integer value n, implement the myPow(x, n) function, which calculates x raised to the power n.

You may not use any built-in library functions.

Example 1:

Input: x = 2.00000, n = 5

Output: 32.00000

Example 2:

Input: x = 1.10000, n = 10

Output: 2.59374

Example 3:

Input: x = 2.00000, n = -3

Output: 0.12500

Constraints:

-100.0 < x < 100.0
-1000 <= n <= 1000
n is an integer.
If x = 0, then n will be positive.

Topics

Math Recursion

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(logn) time and O(logn) space, where n is the given integer.

Hint 1

A brute force approach would be to iterate linearly up to n, multiplying by x each time to find (x^n). If n is negative, return (1 / (x^n)); otherwise, return (x^n). Can you think of a better way? Maybe a recursive approach would be more efficient.

Hint 2

For example, to calculate 2^6, instead of multiplying 2 six times, we compute 2^3 and square the result. The same logic applies recursively to find 2^3 and further break down the multiplication. What should be the base case for this recursion? Maybe you should consider the term that cannot be further broken down.

Hint 3

In (x^n), if x is 0, we return 0. If n is 0, we return 1, as any number raised to the power of 0 is 1. Otherwise, we compute (x^(n/2)) recursively and square the result. If n is odd, we multiply the final result by x. What should be the logic if n is negative?

Hint 4

We start the recursion with the absolute value of n. After computing the result as res, we return res if n is non-negative; otherwise, we return (1 / res).

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion and Divide-and-Conquer - Breaking a problem in half repeatedly to reduce complexity
Binary Exponentiation - The mathematical property that x^n = (x^2)^(n/2) for even n
Bit Manipulation Basics - Using bitwise AND and right shift to check odd/even and halve values
Handling Edge Cases - Managing negative exponents and integer overflow when negating values

1. Brute Force

Intuition

We are asked to compute ( x^n ), where:

x is a floating-point number
n can be positive, zero, or negative

The most straightforward way to think about exponentiation is:

multiplying x by itself n times

This brute force approach directly follows the mathematical definition of power:

if n is positive → multiply x repeatedly
if n is zero → the result is always 1
if n is negative → compute ( x^{|n|} ) and take its reciprocal

Although this method is not efficient for large n, it is very easy to understand and is a good starting point.

Algorithm

Handle edge cases:
- If x == 0, return 0
- If n == 0, return 1
Initialize res = 1 to store the result.
Repeat abs(n) times:
- multiply res by x
If n is positive:
- return res
If n is negative:
- return 1 / res

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

        res = 1
        for i in range(abs(n)):
            res *= x
        return res if n >= 0 else 1 / res

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

        double res = 1;
        for (int i = 0; i < Math.abs(n); i++) {
            res *= x;
        }
        return n >= 0 ? res : 1 / res;
    }
}

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

        double res = 1;
        for (int i = 0; i < abs(n); i++) {
            res *= x;
        }
        return n >= 0 ? res : 1 / res;
    }
};

class Solution {
    /**
     * @param {number} x
     * @param {number} n
     * @return {number}
     */
    myPow(x, n) {
        if (x === 0) {
            return 0;
        }
        if (n === 0) {
            return 1;
        }

        let res = 1;
        for (let i = 0; i < Math.abs(n); i++) {
            res *= x;
        }
        return n >= 0 ? res : 1 / res;
    }
}

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

        double res = 1;
        for (int i = 0; i < Math.Abs(n); i++) {
            res *= x;
        }
        return n >= 0 ? res : 1 / res;
    }
}

func myPow(x float64, n int) float64 {
    if x == 0 {
        return 0
    }
    if n == 0 {
        return 1
    }

    res := 1.0
    for i := 0; i < int(math.Abs(float64(n))); i++ {
        res *= x
    }

    if n >= 0 {
        return res
    }
    return 1 / res
}

class Solution {
    fun myPow(x: Double, n: Int): Double {
        if (x == 0.0) {
            return 0.0
        }
        if (n == 0) {
            return 1.0
        }

        var res = 1.0
        for (i in 0 until Math.abs(n)) {
            res *= x
        }

        return if (n >= 0) res else 1 / res
    }
}

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 {
            return 0
        }
        if n == 0 {
            return 1
        }

        var res: Double = 1
        for _ in 0..<abs(n) {
            res *= x
        }
        return n >= 0 ? res : 1 / res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Exponentiation (Recursive)

Intuition

Computing ( x^n ) by multiplying x repeatedly works, but it becomes very slow when n is large.

A much better idea is to use binary exponentiation, which is based on these observations:

If n is even:
- ( x^n = (x^2)^{n/2} )
If n is odd:
- ( x^n = x \times (x^2)^{(n-1)/2} )

This means we can:

halve the exponent at each step
square the base accordingly

By doing this recursively, the number of multiplications reduces from O(n) to O(log n).

We also handle negative powers by:

computing ( x^{|n|} )
taking the reciprocal if n is negative

Algorithm

Define a recursive helper function helper(x, n):
- If x == 0, return 0
- If n == 0, return 1
Recursively compute:
- res = helper(x * x, n // 2)
If n is odd:
- return x * res
If n is even:
- return res
Call helper(x, abs(n)) to compute the magnitude.
If n is negative:
- return 1 / result
Otherwise:
- return result

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

            res = helper(x * x, n // 2)
            return x * res if n % 2 else res

        res = helper(x, abs(n))
        return res if n >= 0 else 1 / res

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

        double res = helper(x, Math.abs((long) n));
        return (n >= 0) ? res : 1 / res;
    }

    private double helper(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double half = helper(x, n / 2);
        return (n % 2 == 0) ? half * half : x * half * half;
    }
}

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

        double res = helper(x, abs(static_cast<long>(n)));
        return (n >= 0) ? res : 1 / res;
    }

private:
    double helper(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double half = helper(x, n / 2);
        return (n % 2 == 0) ? half * half : x * half * half;
    }
};

class Solution {
    /**
     * @param {number} x
     * @param {number} n
     * @return {number}
     */
    myPow(x, n) {
        /**
         * @param {number} x
         * @param {number} n
         * @return {number}
         */
        function helper(x, n) {
            if (x === 0) {
                return 0;
            }
            if (n === 0) {
                return 1;
            }

            const res = helper(x * x, Math.floor(n / 2));
            return n % 2 === 0 ? res : x * res;
        }

        const res = helper(x, Math.abs(n));
        return n >= 0 ? res : 1 / res;
    }
}

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

        double res = Helper(x, Math.Abs((long) n));
        return (n >= 0) ? res : 1 / res;
    }

    private double Helper(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double half = Helper(x, n / 2);
        return (n % 2 == 0) ? half * half : x * half * half;
    }
}

func myPow(x float64, n int) float64 {
    var helper func(x float64, n int) float64
    helper = func(x float64, n int) float64 {
        if x == 0 {
            return 0
        }
        if n == 0 {
            return 1
        }

        res := helper(x*x, n/2)
        if n%2 != 0 {
            return x * res
        }
        return res
    }

    res := helper(x, int(math.Abs(float64(n))))
    if n >= 0 {
        return res
    }
    return 1 / res
}

class Solution {
    fun myPow(x: Double, n: Int): Double {
        fun helper(x: Double, n: Int): Double {
            if (x == 0.0) {
                return 0.0
            }
            if (n == 0) {
                return 1.0
            }

            val res = helper(x * x, n / 2)
            return if (n % 2 != 0) x * res else res
        }

        val res = helper(x, Math.abs(n))
        return if (n >= 0) res else 1 / res
    }
}

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        func helper(_ x: Double, _ n: Int) -> Double {
            if x == 0 {
                return 0
            }
            if n == 0 {
                return 1
            }

            let res = helper(x * x, n / 2)
            return n % 2 == 0 ? res : x * res
        }

        let res = helper(x, abs(n))
        return n >= 0 ? res : 1 / res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

3. Binary Exponentiation (Iterative)

Intuition

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.

Algorithm

Handle edge cases:
- If x == 0, return 0
- If n == 0, return 1
Initialize:
- res = 1 (stores the final answer)
- power = abs(n) (work with positive exponent)
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
If n is negative:
- return 1 / res
Otherwise:
- return res

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

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

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

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

        return n >= 0 ? res : 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;
    }
};

class Solution {
    /**
     * @param {number} x
     * @param {number} n
     * @return {number}
     */
    myPow(x, n) {
        if (x === 0) return 0;
        if (n === 0) return 1;

        let res = 1;
        let power = Math.abs(n);

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

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

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

        double res = 1;
        long power = Math.Abs((long)n);

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

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

func myPow(x float64, n int) float64 {
    if x == 0 {
        return 0
    }
    if n == 0 {
        return 1
    }

    res := 1.0
    power := int(math.Abs(float64(n)))

    for power > 0 {
        if power&1 != 0 {
            res *= x
        }
        x *= x
        power >>= 1
    }

    if n >= 0 {
        return res
    }
    return 1 / res
}

class Solution {
    fun myPow(x: Double, n: Int): Double {
        var x = x
        if (x == 0.0) {
            return 0.0
        }
        if (n == 0) {
            return 1.0
        }

        var res = 1.0
        var power = Math.abs(n.toLong())

        while (power > 0) {
            if (power and 1 != 0L) {
                res *= x
            }
            x *= x
            power = power shr 1
        }

        return if (n >= 0) res else 1.0 / res
    }
}

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 {
            return 0
        }
        if n == 0 {
            return 1
        }

        var res: Double = 1
        var base = x
        var power = abs(n)

        while power > 0 {
            if power & 1 == 1 {
                res *= base
            }
            base *= base
            power >>= 1
        }

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

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

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.

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.