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 <= 104The Pow(x, n) problem requires computing x^n efficiently, especially when n is very large. A naive approach multiplies x by itself n times, resulting in O(n) time complexity, which becomes inefficient for large inputs.
A better strategy is Exponentiation by Squaring, which reduces the number of multiplications by repeatedly dividing the exponent. If n is even, we compute x^(n/2) once and square the result. If n is odd, we multiply x with x^(n-1). This divide‑and‑conquer technique works naturally with recursion or can be implemented iteratively.
Another important detail is handling negative powers. When n is negative, the result becomes 1 / x^|n|. By halving the exponent at each step, the algorithm runs in O(log n) time, making it significantly faster and suitable for coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive Multiplication | O(n) | O(1) |
| Exponentiation by Squaring (Recursion/Divide & Conquer) | O(log n) | O(log n) |
| Exponentiation by Squaring (Iterative) | O(log n) | O(1) |
take U forward
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.
Time Complexity: O(log n), Space Complexity: O(1)
1#include <stdio.h>
2
3double myPow(double x, int n) {
4 long long N = n;
5 if (
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.
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.
Time Complexity: O(log n), Space Complexity: O(log n) due to the call stack
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly asked in technical interviews because it tests understanding of recursion, divide-and-conquer techniques, and mathematical optimization such as exponentiation by squaring.
This problem does not require a special data structure. It mainly relies on mathematical logic and recursion or iteration to repeatedly halve the exponent and compute powers efficiently.
The optimal approach is Exponentiation by Squaring. It reduces the number of multiplications by dividing the exponent in half at each step, achieving O(log n) time complexity instead of O(n).
When the exponent n is negative, the result becomes the reciprocal of the positive power. In practice, you compute x^|n| using the same efficient approach and then return 1 divided by that result.
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.