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: Implement pow(x, n), which returns x raised to the power n. The tricky part is handling large exponents and negative powers efficiently without multiplying x exactly n times.
Approach 1: Naive Multiplication (O(n) time, O(1) space)
The simplest strategy repeatedly multiplies x by itself n times. Start with a result value of 1, iterate from 1 to n, and update result *= x. If n is negative, compute the power for |n| and return 1/result. This approach is straightforward but inefficient for large values of n because it performs n multiplications. It demonstrates the core idea of exponentiation but quickly becomes too slow when n is large.
Approach 2: Iterative Exponentiation by Squaring (O(log n) time, O(1) space)
This optimized approach reduces the number of multiplications using the mathematical identity: x^n = (x^2)^(n/2). Instead of multiplying x repeatedly, square the base while halving the exponent. If the current exponent is odd, multiply the result by the current base before squaring. Continue shifting the exponent using integer division until it becomes zero. This technique processes the exponent bit-by-bit, similar to binary exponentiation, which cuts the number of operations from n to log₂(n). It works well for very large powers and avoids recursion overhead. The algorithm relies purely on arithmetic operations from Math concepts.
Approach 3: Recursive Divide and Conquer (O(log n) time, O(log n) space)
The recursive version follows the same exponentiation-by-squaring principle but expresses it with recursion. Compute half = pow(x, n/2). If n is even, return half * half. If n is odd, multiply once more with x. For negative exponents, convert the problem using x^-n = 1 / x^n. Each recursive call halves the exponent, producing a recursion depth of log₂(n). This approach is clean and easy to reason about because it directly mirrors the mathematical recurrence, making it a common demonstration of recursion and divide-and-conquer strategies.
Recommended for interviews: Interviewers usually expect exponentiation by squaring with O(log n) complexity. The iterative version is slightly preferred because it avoids recursion stack overhead and shows awareness of performance tradeoffs. Explaining the naive O(n) method first demonstrates understanding of the problem, while transitioning to the logarithmic solution shows algorithmic optimization skills.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n), Space Complexity: O(log n) due to the call stack
| 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 |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Multiplication | O(n) | O(1) | For understanding the basic concept of exponentiation or when n is very small |
| Iterative Exponentiation by Squaring | O(log n) | O(1) | Best general solution for large exponents and interview settings |
| Recursive Divide and Conquer | O(log n) | O(log n) | When recursion is preferred for clarity or when demonstrating divide-and-conquer |
POW(x,n) | Binary Exponentiation | Leetcode • take U forward • 273,811 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