💬 Discord
Sign In
NeetCode #915LC-50MediumMath & GeometryNC 150NC 250
← Back to All Problems

#915 · #50 · Pow(x, n)(Pow(x, n)

📌 Problem Statement & Constraints

Implement pow(x, n), computing x raised to the integer power n, without using any built-in power function. Constraints: -100.0 < x < 100.0, -2^31 <= n <= 2^31 - 1, and x^n is guaranteed to fit in the result range.

💡 Core Algorithmic Approaches

  1. Use binary exponentiation (fast power): x^n = (x^2)^(n/2) when n is even and x * x^(n-1) when n is odd.
  2. Handle a negative exponent by inverting the base and negating the exponent: x^-n = (1/x)^n.
  3. Iteratively square the base and halve the exponent, multiplying the running result whenever the lowest bit of the exponent is set.
  4. This reduces the number of multiplications from n to log2(n), which is essential since n can be about 2 billion.

💻 Benchmark Python3 Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1.0
        while n:
            if n & 1:              # current bit set -> multiply in this power
                result *= x
            x *= x                 # square the base
            n >>= 1                # move to the next bit
        return result

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): the exponent is halved every iteration.
💾 Space Complexity
O(1): the iterative form uses only a few scalars (a recursive version would use O(log n) stack).

⚠️ Interview Pitfalls & Follow-ups

  • Ignoring a negative exponent: x^-n = (1/x)^n; skipping this returns a wildly wrong value.
  • Negating n in a fixed-width language when n = -2^31: the negation overflows the minimum int; Python's unbounded integers are safe.
  • Testing the bit after shifting: the bit test must use the current value of n before n >>= 1.
  • Adding a special case for n == 0: the loop already returns 1.0, so the branch is dead code.