Pow(x, n)

LeetCode 50: Pow(x, n) Solution & Explanation

Problem Overview

TL;DR: Convert negative exponents using a reciprocal, then use exponentiation by squaring while reading the exponent bit by bit to compute the result in O(log |n|) time.

LeetCode 50, Pow(x, n), asks you to compute x^n for a floating-point base x and a 32-bit signed integer exponent n. The exponent may be positive, zero, or negative, and the result must be returned as a floating-point value within the accepted numerical error.

This LeetCode 50 Solution uses the binary representation of the exponent. Each set bit identifies a power of x that belongs in the final product, while repeated squaring generates those powers efficiently. This is a popular interview question because it tests exponent manipulation, bitwise operations, numerical edge cases, and the optimal solution for interviews.

Brute Force Approach for Pow(x, n)

The direct approach multiplies the base by itself once for every unit in the absolute value of the exponent.

For a non-negative exponent:

result = 1

repeat n times:
    result = result * x

return result

For a negative exponent, compute the positive power first and then take its reciprocal:

if n < 0:
    result = 1
    repeat -n times:
        result = result * x
    return 1 / result

return result

The time complexity is:

O(|n|)

The exponent can be as large as 2^31 - 1, so this method may require billions of multiplications. That causes a Time Limit Exceeded error and does not meet the expected efficiency for LeetCode 50. The solution must reduce the number of multiplication steps from linear in |n| to logarithmic in |n|.

Algorithm Strategy: Bit Manipulation Patterns

1. Store the exponent in a sufficiently wide integer type where necessary.
2. If the exponent is negative:
   • Replace x with 1 / x.
   • Negate the exponent.
3. Initialize result to 1.0.
4. While the exponent is greater than zero:
   • Inspect its least significant bit.
   • If that bit is 1, multiply result by the current base.
   • Square the current base.
   • Shift the exponent right by one bit.
5. Return result.

The exponent bits determine which squared powers are included. The right shift guarantees that every bit is processed exactly once, and repeated squaring guarantees that the current base always corresponds to the next power of two.

Execution Flow

For x = 2 and n = 13:

1. The exponent is positive, so the base remains 2.
2. Initialize:
   textCopy

   result = 1
   x = 2
   exponent = 13  // binary 1101

3. The least significant bit of 13 is 1:
   • Multiply result by 2.
   • Square the base to 4.
   • Shift 13 right to 6.
4. The least significant bit of 6 is 0:
   • Do not change result.
   • Square the base to 16.
   • Shift 6 right to 3.
5. The least significant bit of 3 is 1:
   • Multiply result by 16.
   • Square the base to 256.
   • Shift 3 right to 1.
6. The least significant bit of 1 is 1:
   • Multiply result by 256.
   • Shift the exponent to 0.
7. Stop and return:
   textCopy

   2 * 16 * 256 = 8192 = 2^13

For a negative exponent such as n = -3:

1. Replace x with 1 / x.
2. Convert the exponent to 3.
3. Run the same bitwise loop.
4. Return (1 / x)^3, which equals x^-3.

When n is zero, the loop executes zero times and the initial value result = 1.0 is returned.

Proof of Correctness

Let the original normalized exponent be N, where N >= 0.

At the beginning of each iteration:

• result contains the product of the powers corresponding to all previously processed set bits.
• x equals the original normalized base raised to 2^k, where k is the number of processed bits.
• exponent contains the remaining bits of N after removing the lowest k bits.

If the current least significant bit is 1, the current power x is part of the binary decomposition of N, so multiplying it into result preserves the correct product. If the bit is 0, no multiplication is needed.

Afterward:

• Squaring x changes it from the power base^(2^k) to base^(2^(k+1)).
• Right-shifting exponent removes the processed bit and exposes the next bit.

Thus, the invariant remains true after every iteration. When exponent becomes zero, all bits of N have been processed, so result equals the normalized base raised to N.

For an original negative exponent, the algorithm first uses:

x^n = (1 / x)^(-n)

Therefore, the same proof applies after normalization. If n is zero, no bits are processed and the initialized result 1.0 is mathematically correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 342: Power of Four
• LeetCode 231: Power of Two

Both problems inspect binary structure using bitwise operations. Power of Two checks whether exactly one bit is set, while Power of Four adds a positional constraint on that set bit. Pow(x, n) uses the same binary representation principles differently: it processes every exponent bit and uses repeated squaring to construct the corresponding powers.

The Pow(x, n) technique is therefore exponentiation by squaring guided by bitwise exponent processing, making it a direct example of the Bit Manipulation Patterns curriculum.

Reference Implementation

C++ Solution for LeetCode 50

1class Solution {
2public:
3    double myPow(double x, int n) {
4        long long exponent = n;
5        if (exponent < 0) {
6            x = 1.0 / x;
7            exponent = -exponent;
8        }
9
10        double result = 1.0;
11        while (exponent > 0) {
12            if (exponent & 1LL) {
13                result *= x;
14            }
15            x *= x;
16            exponent >>= 1;
17        }
18        return result;
19    }
20};

The long long exponent safely handles n = -2^31. The expression exponent & 1LL checks whether the current exponent bit is set, and exponent >>= 1 removes that bit after processing.

Java Solution for LeetCode 50

1class Solution {
2    public double myPow(double x, int n) {
3        long exponent = n;
4        if (exponent < 0) {
5            x = 1.0 / x;
6            exponent = -exponent;
7        }
8
9        double result = 1.0;
10        while (exponent > 0) {
11            if ((exponent & 1) != 0) {
12                result *= x;
13            }
14            x *= x;
15            exponent >>= 1;
16        }
17
18        return result;
19    }
20}

Java promotes n to long before negation, preventing overflow for the minimum integer value. The loop uses the same bit inspection, squaring, and right-shift transitions as the C++ version.

Python Solution for LeetCode 50

1class Solution:
2    def myPow(self, x: float, n: int) -> float:
3        if n < 0:
4            x = 1.0 / x
5            n = -n
6
7        result = 1.0
8        while n > 0:
9            if n & 1:
10                result *= x
11            x *= x
12            n >>= 1
13
14        return result

Python integers automatically support values beyond the 32-bit range, so negating the minimum exponent does not overflow. The bitwise loop directly mirrors the C++ and Java implementations.