Pow(x, n)
Understanding the Problem
We need to compute x raised to the power n, where x is a floating-point number and n is a 32-bit integer. Two details complicate the naive solution.
First, n can be negative. When n is negative, x^n = 1 / x^(-n), so we need to handle that conversion. Second, n can be large in magnitude, up to 2^31 - 1 (about 2.1 billion). Multiplying x by itself n times in a loop would be too slow.
Exponentiation has a divide-and-conquer structure that avoids the linear loop. Instead of multiplying x one factor at a time, we square intermediate results to skip ahead. For example, x^10 = (x^5)^2, and x^5 = x * (x^2)^2. This computes the answer in O(log n) multiplications instead of O(n).
Key Constraints:
-2^31 <= n <= 2^31 - 1--> n can be up to ~2.1 billion, so an O(n) loop will time out. We need O(log n).-100.0 < x < 100.0--> x is bounded, so intermediate results won't overflow to infinity for valid inputs where x^n is within [-10^4, 10^4].ncan be negative --> We need to handle the conversion x^(-n) = 1 / x^n.- When
n = -2^31, negating it overflows a signed 32-bit integer, since the positive range stops at 2^31 - 1 --> hold the magnitude in a 64-bit type.
Approach 1: Brute Force (Linear Multiplication)
Intuition
Compute x^n by multiplying x by itself n times. If n is negative, replace x with 1/x so the loop can run a positive number of times.
This is correct but runs in O(n). With n up to 2 billion, it is too slow to pass.
Algorithm
- If n is 0, return 1 (anything raised to the power 0 is 1)
- If n is negative, set x to 1/x and n to -n (use a long to avoid integer overflow)
- Initialize result to 1.0
- Multiply result by x, n times
- Return result
Example Walkthrough
Input: x = 2.0, n = 4
We multiply 2.0 by itself 4 times:
- result = 1.0
- result = 1.0 * 2.0 = 2.0
- result = 2.0 * 2.0 = 4.0
- result = 4.0 * 2.0 = 8.0
- result = 8.0 * 2.0 = 16.0
Output: 16.0
Code
- Time Complexity: O(n). We perform exactly |n| multiplications, one per loop iteration.
- Space Complexity: O(1). We only use a few variables regardless of input size.
This performs |n| multiplications one at a time and ignores the structure of exponentiation. The next approach halves the exponent at each step by squaring intermediate results.
Approach 2: Recursive Binary Exponentiation
Intuition
Exponentiation has a recursive structure that cuts the exponent in half at every step.
If n is even: x^n = (x^(n/2))^2. Compute x^(n/2) once, then square it.
If n is odd: x^n = x x^(n-1) = x (x^((n-1)/2))^2. Compute x^((n-1)/2), square it, and multiply by x one more time.
Either way, the exponent drops to about half in each recursive call. Starting from n, it reaches 0 after about log2(n) steps. That brings the cost from O(n) multiplications down to O(log n). The base case is x^0 = 1.
For negative exponents, convert up front: x^(-n) = (1/x)^n. If n is the minimum 32-bit value (-2^31), negating it overflows a signed 32-bit int because the positive range only reaches 2^31 - 1. Holding the absolute value in a long (or equivalent 64-bit type) avoids that.
The recurrence is exact, not approximate. For even n, n/2 is an integer and (x^(n/2))^2 = x^n follows from the exponent laws. For odd n, integer division gives n/2 = (n-1)/2, so (x^(n/2))^2 = x^(n-1), and one extra factor of x recovers x^n. Every call reduces n by at least half, so the recursion terminates at n = 0 after at most log2(n) + 1 calls.
Algorithm
- Handle the negative exponent: if n < 0, replace x with 1/x and n with -n (using a long to avoid overflow)
- Call a recursive helper with x and the positive exponent
- Base case: if n equals 0, return 1.0
- Recursive step: compute half = helper(x, n / 2)
- If n is even, return half * half
- If n is odd, return half half x
Example Walkthrough
Code
- Time Complexity: O(log n). We halve the exponent at each recursive step, making at most log2(n) + 1 calls. Each call does O(1) work.
- Space Complexity: O(log n). The recursion stack goes log2(n) levels deep. For n = 2^31, that is about 31 stack frames.
The recursion uses O(log n) stack space. The next approach performs the same halving in an iterative loop, dropping the space to O(1).
Approach 3: Iterative Binary Exponentiation (Optimal)
Intuition
The same halving can run iteratively by reading the binary representation of n directly.
Write n in binary. For example, n = 13 is 1101 in binary, meaning 13 = 8 + 4 + 1. So x^13 = x^8 x^4 x^1. The powers x^1, x^2, x^4, x^8 come from repeatedly squaring x. The result is the product of the powers whose bit in n is 1.
The loop scans the bits of n from least significant to most significant. A variable currentProduct starts at x and is squared each iteration, so at step i it equals x^(2^i). When the current bit of n is 1, currentProduct is multiplied into the running result.
This has the same O(log n) time as the recursive approach, with O(1) space since there is no recursion stack.
Every integer n is a sum of distinct powers of 2, one per set bit. For n = 13 = 2^3 + 2^2 + 2^0, the exponent law gives x^13 = x^(8+4+1) = x^8 x^4 x^1. Squaring currentProduct at each step keeps the invariant currentProduct = x^(2^i) when the loop is examining bit i. Including that factor exactly when bit i is set reproduces the sum-of-powers decomposition, so the running product equals x^n once all set bits have been processed.
Algorithm
- Handle the negative exponent: if n < 0, replace x with 1/x and work with |n| (use a long to avoid overflow)
- Initialize result to 1.0 and currentProduct to x
- While the exponent is greater than 0:
- If the current bit (exponent & 1) is 1, multiply result by currentProduct
- Square currentProduct (it now represents the next power of x)
- Right-shift the exponent by 1 (equivalent to dividing by 2)
- Return result
Example Walkthrough
Code
- Time Complexity: O(log n). We process each bit of n exactly once. A 32-bit integer has at most 31 significant bits, so this runs in at most ~31 iterations.
- Space Complexity: O(1). We only use a constant number of variables. No recursion stack, no additional data structures.