Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Pow(x, n)

MEDIUMProblemSolveExternal Links

Description

Implement a function that computes x raised to the power n (written as xⁿ). This is the standard mathematical exponentiation operation.

The base x is a floating-point number and the exponent n is an integer that can be positive, negative, or zero. When n is negative, the result equals the reciprocal of x raised to the absolute value of n: x⁻ⁿ = 1 / xⁿ. When n is zero, the result is 1 for any non-zero x.

Your solution must handle the full range of 32-bit integer exponents efficiently — a naive approach that multiplies x by itself n times will be far too slow for large n.

Examples

Example 1

Input: x = 2.00000, n = 10

Output: 1024.00000

Explanation: 2 multiplied by itself 10 times equals 1024. Notice that 10 in binary is 1010, which hints at a faster approach using repeated squaring.

Example 2

Input: x = 2.10000, n = 3

Output: 9.26100

Explanation: 2.1 × 2.1 × 2.1 = 9.261. The function works with floating-point bases, not just integers.

Example 3

Input: x = 2.00000, n = -2

Output: 0.25000

Explanation: 2⁻² = 1 / 2² = 1 / 4 = 0.25. A negative exponent means computing the positive power first and then taking its reciprocal.

Constraints

  • -100.0 < x < 100.0
  • -2³¹ ≤ n ≤ 2³¹ - 1
  • n is an integer
  • Either x is not zero or n > 0
  • -10⁴ ≤ xⁿ ≤ 10⁴

Editorial

Brute Force - Linear Multiplication

Intuition

The most straightforward way to compute xⁿ is to multiply x by itself n times. Start with a result of 1.0 and keep multiplying by x in a loop.

For negative exponents, we use the mathematical identity x⁻ⁿ = 1 / xⁿ. So we either flip x to 1/x at the start and use |n|, or compute the positive power first and take its reciprocal at the end.

This is exactly how you would compute a power by hand: to find 2¹⁰, you would write 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 and multiply step by step.

Step-by-Step Explanation

Let's trace through with x = 2.0, n = 10:

Step 1: Initialize result = 1.0. We need to multiply by x = 2.0 exactly 10 times.

Step 2: Iteration 1: result = 1.0 × 2.0 = 2.0

Step 3: Iteration 2: result = 2.0 × 2.0 = 4.0

Step 4: Iteration 3: result = 4.0 × 2.0 = 8.0

Step 5: Iteration 4: result = 8.0 × 2.0 = 16.0

Step 6: Iteration 5: result = 16.0 × 2.0 = 32.0

Step 7: Iterations 6 through 10: result goes 32.0 → 64.0 → 128.0 → 256.0 → 512.0 → 1024.0

Step 8: After 10 multiplications, result = 1024.0. Return 1024.0.

Now let's trace a negative exponent with x = 2.0, n = -2:

Step 9: n is negative, so we flip x: x = 1/2.0 = 0.5, and use |n| = 2.

  • Iteration 1: result = 1.0 × 0.5 = 0.5
  • Iteration 2: result = 0.5 × 0.5 = 0.25

Step 10: Return 0.25, which equals 2⁻² = 1/4.

Algorithm

  1. Convert n to a long integer to safely handle n = -2³¹ (negating it would overflow a 32-bit int)
  2. If n is negative, set x = 1/x and use |n|
  3. Initialize result = 1.0
  4. Loop |n| times, multiplying result by x at each iteration
  5. Return result

Code

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1.0 / x;
            N = -N;
        }
        double result = 1.0;
        for (long long i = 0; i < N; i++) {
            result *= x;
        }
        return result;
    }
};
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1.0 / x
            n = -n
        result = 1.0
        for _ in range(n):
            result *= x
        return result
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1.0 / x;
            N = -N;
        }
        double result = 1.0;
        for (long i = 0; i < N; i++) {
            result *= x;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We perform exactly |n| multiplications, one per loop iteration. When n can be up to 2³¹ - 1, this means up to about 2.1 billion operations.

Space Complexity: O(1)

We use only a single variable (result) to accumulate the product. No additional memory grows with the input.

Why This Approach Is Not Efficient

The brute force requires exactly |n| multiplications. Since n can reach 2³¹ - 1 (about 2.1 billion), this means up to 2.1 billion floating-point multiplications. Even at hundreds of millions of operations per second, this would take several seconds — far too slow.

The core inefficiency is that we compute each intermediate power from scratch. To get x¹⁰, we do x × x × x × ... ten times. But notice that x⁴ = x² × x², and x⁸ = x⁴ × x⁴. By squaring already-computed powers, we can jump from x² to x⁴ to x⁸ in just two steps instead of six.

This observation leads to the halving strategy: reduce n by half at each step, cutting the total work from O(n) to O(log n).

Chart comparing O(n) linear multiplication versus O(log n) binary exponentiation for various exponent sizes
Chart comparing O(n) linear multiplication versus O(log n) binary exponentiation for various exponent sizes

Better Approach - Recursive Halving

Intuition

Instead of multiplying one at a time, we can halve the exponent at each step using fundamental properties of exponents:

  • If n is even: xⁿ = (x × x)^(n/2). Square the base and halve the exponent.
  • If n is odd: xⁿ = x × (x × x)^((n-1)/2). Pull out one factor of x, then apply the even case.

For example, to compute 2¹⁰:

  • 2¹⁰ → n is even → (2×2)⁵ = 4⁵
  • 4⁵ → n is odd → 4 × (4×4)² = 4 × 16²
  • 16² → n is even → (16×16)¹ = 256¹
  • 256¹ → n is odd → 256 × 1 = 256
  • Unwind: 4 × 256 = 1024

Notice how n shrinks from 10 → 5 → 2 → 1 → 0 in just 4 steps. In general, we need only about log₂(n) recursive calls, because each call at least halves n.

Step-by-Step Explanation

Let's trace pow(2.0, 10) with recursive halving:

Step 1: Call pow(2, 10). n=10 is even. Apply rule: pow(x², n/2) = pow(4, 5).

Step 2: Call pow(4, 5). n=5 is odd. Extract factor: 4 × pow(16, 2).

Step 3: Call pow(16, 2). n=2 is even. Apply rule: pow(256, 1).

Step 4: Call pow(256, 1). n=1 is odd. Extract factor: 256 × pow(65536, 0).

Step 5: Call pow(65536, 0). Base case: n=0, return 1.

Step 6: Unwind: pow(256, 1) = 256 × 1 = 256.

Step 7: Unwind: pow(16, 2) = 256 (directly from the recursive result).

Step 8: Unwind: pow(4, 5) = 4 × 256 = 1024.

Step 9: Unwind: pow(2, 10) = 1024. Only 4 recursive calls and about 5 multiplications total, compared to 10 in brute force.

Recursive Halving — Watching the Exponent Shrink — Watch how each recursive call either halves the exponent (when even) or subtracts one and halves (when odd), rapidly reducing the problem size. The tree shows the call chain and the values returned as we unwind.

Algorithm

  1. If n is negative, compute 1 / helper(x, -n)
  2. Helper function (handles non-negative exponents):
    a. Base case: If n == 0, return 1.0
    b. Even case: If n is even, return helper(x × x, n / 2)
    c. Odd case: If n is odd, return x × helper(x × x, (n - 1) / 2)
  3. Return the result from helper

Code

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

private:
    double helper(double x, long long n) {
        if (n == 0) return 1.0;
        if (n % 2 == 0) {
            return helper(x * x, n / 2);
        } else {
            return x * helper(x * x, (n - 1) / 2);
        }
    }
};
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(base: float, exp: int) -> float:
            if exp == 0:
                return 1.0
            if exp % 2 == 0:
                return helper(base * base, exp // 2)
            else:
                return base * helper(base * base, (exp - 1) // 2)

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

    private double helper(double x, long n) {
        if (n == 0) return 1.0;
        if (n % 2 == 0) {
            return helper(x * x, n / 2);
        } else {
            return x * helper(x * x, (n - 1) / 2);
        }
    }
}

Complexity Analysis

Time Complexity: O(log n)

Each recursive call at least halves the exponent. Starting from n, after k calls the exponent is at most n / 2ᵏ, which reaches 0 when k = log₂(n). Each call does O(1) work (one or two multiplications).

Space Complexity: O(log n)

The recursion stack goes log₂(n) levels deep. For the maximum exponent n = 2³¹, this means at most 31 stack frames — manageable in practice but not strictly constant.

Why This Approach Is Not Efficient

The recursive halving approach reduces time from O(n) to O(log n) — a massive improvement. For n = 2³¹, this means about 31 operations instead of 2 billion.

However, the recursion uses O(log n) stack space. While 31 stack frames is practically harmless, an iterative version achieves the same O(log n) time with only O(1) extra space. The iterative approach also avoids function-call overhead and is typically marginally faster.

More importantly, the iterative version reveals an elegant connection between the binary representation of n and the powers we need to multiply. Instead of thinking recursively about even/odd cases, we can directly inspect which bits of n are set and multiply the corresponding powers of x — a technique called binary exponentiation.

Optimal Approach - Iterative Binary Exponentiation

Intuition

Every positive integer can be written as a sum of distinct powers of 2 — its binary representation. This means xⁿ can be decomposed into a product of powers of x that are themselves powers of 2.

For example, n = 10 = 1010₂ = 2³ + 2¹ = 8 + 2. Therefore:

x¹⁰ = x⁸⁺² = x⁸ × x²

We can compute x¹, x², x⁴, x⁸ by repeatedly squaring (each step doubles the exponent), and then multiply together only the powers corresponding to the '1' bits in n's binary representation.

The algorithm processes n's bits from right (least significant) to left. A running variable base starts at x and doubles in power each iteration (x → x² → x⁴ → x⁸ → ...). Whenever we encounter a '1' bit, we fold the current base value into our result.

Diagram showing how the exponent 10 decomposes into binary 1010 and how x^10 equals x^8 times x^2
Diagram showing how the exponent 10 decomposes into binary 1010 and how x^10 equals x^8 times x^2

Step-by-Step Explanation

Let's trace pow(2.0, 10) using iterative binary exponentiation:

Step 1: Convert n=10 to binary: 1010₂. Set up: result = 1.0, base = 2.0. We process bits right to left.

Step 2: Bit 0 (rightmost) is 0. x¹ = 2 is NOT needed. Skip. Square base: 2.0 → 4.0 (now represents x²).

Step 3: Bit 1 is 1. x² = 4 IS needed. Multiply result: 1.0 × 4.0 = 4.0. Square base: 4.0 → 16.0 (now x⁴).

Step 4: Bit 2 is 0. x⁴ = 16 is NOT needed. Skip. Square base: 16.0 → 256.0 (now x⁸).

Step 5: Bit 3 is 1. x⁸ = 256 IS needed. Multiply result: 4.0 × 256.0 = 1024.0. Square base: 256.0 → 65536.0.

Step 6: No more bits. Final result = 1024.0. We used 5 multiplications total: 3 squarings and 2 result multiplications.

Binary Exponentiation — Processing Bits of the Exponent — Watch how we scan the binary representation of n from right to left. For each '1' bit, we include the current power of x in the result. The base doubles in power at every step through squaring.

Algorithm

  1. Convert n to a long integer to handle the edge case n = -2³¹
  2. If n is negative, set x = 1/x and use |n|
  3. Initialize result = 1.0 and base = x
  4. While n > 0:
    • If the least significant bit of n is 1 (check with n & 1), multiply result by base
    • Square the base: base = base × base
    • Right-shift n by 1 bit: n >>= 1
  5. Return result

Code

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1.0 / x;
            N = -N;
        }
        double result = 1.0;
        double base = x;
        while (N > 0) {
            if (N & 1) {
                result *= base;
            }
            base *= base;
            N >>= 1;
        }
        return result;
    }
};
class Solution:
    def myPow(self, x: float, n: int) -> float:
        N = n
        if N < 0:
            x = 1.0 / x
            N = -N
        result = 1.0
        base = x
        while N > 0:
            if N & 1:
                result *= base
            base *= base
            N >>= 1
        return result
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1.0 / x;
            N = -N;
        }
        double result = 1.0;
        double base = x;
        while (N > 0) {
            if ((N & 1) == 1) {
                result *= base;
            }
            base *= base;
            N >>= 1;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log n)

The while loop processes each bit of n exactly once. Since n has at most log₂(n) + 1 bits, the loop runs O(log n) times. Each iteration performs at most 2 multiplications (one squaring, one optional result multiplication), so the total work is O(log n).

Space Complexity: O(1)

We use only two floating-point variables (result and base) and one integer (N). No recursion stack, no arrays — constant space regardless of input size. This is the key advantage over the recursive approach.