Pow(x, n) - Solution & Explanation
Problem Statement
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-1nis an integer.- Either
xis not zero orn > 0. -104 <= xn <= 104
Approach Overview
Problem 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.
Approach 1: Iterative Method with Exponentiation by Squaring
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.
Complexity
Time Complexity: O(log n), Space Complexity: O(1)
Approach 2: Recursive Divide and Conquer
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.
Complexity
Time Complexity: O(log n), Space Complexity: O(log n) due to the call stack
Approach 3: Mathematics (Fast Powering)
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.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| 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) | — |
Detailed Complexity Analysis
| 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 |
Video Solution
POW(x,n) | Binary Exponentiation | Leetcode • take U forward • 401,334 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Pow(x, n) easy or hard?
Pow(x, n) Python/Java solution
How to solve Pow(x, n) in O(log n)?
What is the best approach for Pow(x, n)?
Is Pow(x, n) asked at Google/Amazon/Meta?
What data structure is used in Pow(x, n)?
What is the time complexity of Pow(x, n)?
Ready to solve this problem?
Practice Pow(x, n) with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor