Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10 Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3 Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
-100.0 < x < 100.0-231 <= n <= 231-1n is an integer.x is not zero or n > 0.-104 <= xn <= 104Problem Overview: The task is to implement pow(x, n), which returns x raised to the power n. The challenge comes from handling very large exponents efficiently, including negative values of n, without relying on built‑in power functions.
Approach 1: Naive Multiplication (O(n) time, O(1) space)
The most straightforward solution multiplies x by itself n times. You iterate from 1 to n, repeatedly updating the result with result *= x. For negative powers, compute 1 / x^|n|. This approach works but becomes extremely slow for large exponents because it performs one multiplication per step. It demonstrates the basic idea but fails typical interview constraints where n may be up to billions.
Approach 2: Iterative Exponentiation by Squaring (O(log n) time, O(1) space)
This optimized approach repeatedly squares the base while halving the exponent. The key observation is that x^n can be written as (x^2)^(n/2) when n is even, and x * x^(n-1) when n is odd. Using this property, you iterate while n > 0, multiply the result when the current bit of the exponent is odd, then square the base and divide the exponent by two. Because the exponent shrinks by half each step, the algorithm runs in logarithmic time. This method relies on simple arithmetic operations and fits naturally within topics like math and efficient power computation.
Approach 3: Recursive Divide and Conquer (O(log n) time, O(log n) space)
The recursive version applies the same exponentiation by squaring logic but expresses it using recursion. If n is even, compute pow(x, n/2) once and square the result. If n is odd, multiply x with the result of pow(x, n-1). The recursion depth is proportional to log n because the exponent is halved each time. The algorithm is clean and closely reflects the mathematical recurrence, making it a common teaching example in recursion and divide and conquer strategies. The tradeoff is additional call stack space compared to the iterative solution.
Recommended for interviews: Interviewers typically expect exponentiation by squaring. Start by explaining the naive multiplication approach to show baseline reasoning, then move to the logarithmic solution. The iterative implementation is usually preferred because it avoids recursion overhead while maintaining O(log n) time and constant space.
The iterative method with exponentiation by squaring is an efficient way to calculate powers. It reduces the time complexity by squaring the base and halving the power at each step. This method leverages the mathematical property that xn = (x2)n/2 when n is even and xn = x * xn - 1 when n is odd. By iteratively updating the base and reducing the power, this method achieves a logarithmic time complexity.
The C solution iteratively calculates the power using a loop. We adjust for negative exponents by taking the reciprocal of x and converting n to positive. This solution uses long long to handle large powers and iteratively squares the base, multiplying it to the result if the current power is odd.
Time Complexity: O(log n), Space Complexity: O(1)
The recursive divide and conquer method further optimizes power calculation by dividing the problem into smaller subproblems. By recursively dividing the power by 2, this approach minimizes the number of multiplications. If the power is even, it computes (xn/2)2, and if odd, it adjusts with an additional multiplication. This recursive approach can be more intuitive, especially for understanding the problem breakdown.
The C recursive solution utilizes a helper function to perform the divide and conquer. The base case is when n equals zero, returning 1. Otherwise, it recurs with half the exponent, and then checks if the exponent is odd, multiplying the result by x.
Time Complexity: O(log n), Space Complexity: O(log n) due to the call stack
The core idea of the fast powering algorithm is to decompose the exponent n into the sum of 1s on several binary bits, and then transform the nth power of x into the product of several powers of x.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the exponent.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Iterative Method with Exponentiation by Squaring | Time Complexity: O(log n), Space Complexity: O(1) |
| Recursive Divide and Conquer | Time Complexity: O(log n), Space Complexity: O(log n) due to the call stack |
| Mathematics (Fast Powering) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Multiplication | O(n) | O(1) | Useful for understanding the basic power computation but inefficient for large exponents |
| Iterative Exponentiation by Squaring | O(log n) | O(1) | Best general solution for interviews and production code |
| Recursive Divide and Conquer | O(log n) | O(log n) | Good when demonstrating recursion or divide-and-conquer concepts |
POW(x,n) | Binary Exponentiation | Leetcode • take U forward • 370,759 views views
Watch 9 more video solutions →Practice Pow(x, n) with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor