Pow(x, n)
MedPrompt
Input: x = 2.00000, n = 10
Output: 1024.00000Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100Example 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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simulates the basic definition of exponentiation by repeatedly multiplying the base x for n times. It's the most straightforward but least efficient method.
Algorithm
- Convert the integer
nto a longNto handle theInteger.MIN_VALUEcase. - If
Nis negative, updatexto1/xandNto-N. - Initialize a variable
ansto1.0. - Iterate from
0toN-1. - In each iteration, multiply
ansbyx. - After the loop, return
ans.
Walkthrough
The algorithm handles three main cases for the exponent n:
- Positive
n: We initialize a result to1.0and multiply it byxexactlyntimes in a loop. nis zero: By definition,x^0is1, so we return1.0.- Negative
n: We use the propertyx^-n = 1 / x^n. To avoid integer overflow whennisInteger.MIN_VALUE, we first convertnto along. Then, we can safely negate it. We calculate the power for the positive exponent-nand then take its reciprocal. A small optimization for the negative case is to compute(1/x)^-ninstead.
public class Solution { public double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } double ans = 1.0; for (long i = 0; i < N; i++) { ans = ans * x; } return ans; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Works correctly for small values of
n.
Cons
Extremely inefficient for large values of
n.Will result in a 'Time Limit Exceeded' (TLE) error on most online judges due to the O(n) complexity.
A more efficient approach is to use the 'Exponentiation by Squaring' method, also known as binary exponentiation. This method leverages the property that x^n = (x^2)^(n/2) if n is even, and x^n = x * (x^2)^((n-1)/2) if n is odd. This significantly reduces the number of multiplications.
Algorithm
- Create a main function
myPow(x, n)that handles the sign ofn. - Convert
nto a longN. IfNis negative, setx = 1/xandN = -N. - Call a recursive helper function
fastPow(x, N). - Inside
fastPow(x, n): - If
nis0, return1.0(base case). - Recursively call
fastPow(x, n / 2)and store the result inhalf. - If
nis even, returnhalf * half. - If
nis odd, returnhalf * half * x.
Walkthrough
This approach is implemented recursively. We define a helper function that calculates the power.
The base case for the recursion is when the exponent n becomes 0, in which case we return 1.0.
In the recursive step, we first calculate the result for n/2, let's call it half. Then, we square half to get half * half. If n is even, this is our result. If n is odd, we need to multiply by an extra x.
The main myPow function handles the sign of n. If n is negative, we calculate 1.0 / fastPow(x, -n). Again, we must be careful with n = Integer.MIN_VALUE. A simple way is to calculate 1.0 / (fastPow(x, -(n+1)) * x) to avoid overflow, or convert n to a long.
public class Solution { private double fastPow(double x, long n) { if (n == 0) { return 1.0; } double half = fastPow(x, n / 2); if (n % 2 == 0) { return half * half; } else { return half * half * x; } } public double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } return fastPow(x, N); }}Complexity
Time
O(log n)
Space
O(log n)
Trade-offs
Pros
Significantly faster than the brute-force approach with logarithmic time complexity.
Elegant and concise recursive solution.
Cons
The recursion depth can be up to
log n, which consumes stack space.For very large
n, this could potentially lead to a stack overflow error, although it's unlikely with the given constraints.
This is the most optimal approach. It uses the same 'Exponentiation by Squaring' principle as the recursive method but implements it iteratively. This eliminates the overhead of recursion and reduces the space complexity to constant.
Algorithm
- Convert
nto a longNto handleInteger.MIN_VALUE. - If
Nis negative, updatexto1/xandNto-N. - Initialize
ansto1.0andcurrent_producttox. - Loop as long as
N > 0. - Inside the loop, check if
Nis odd (N % 2 == 1). If it is, multiplyansbycurrent_product. - Square
current_product(current_product = current_product * current_product). - Halve
Nby integer division (N = N / 2). - After the loop finishes, return
ans.
Walkthrough
The iterative approach works by considering the binary representation of the exponent n. We iterate while n is not zero. In each step, we check if the current least significant bit of n is 1. If it is, we multiply our current result by the current power of x. Then, we square the current power of x and right-shift n by one bit (equivalent to dividing by 2).
For example, to calculate x^13, the binary representation of 13 is 1101. This means x^13 = x^(8+4+1) = x^8 * x^4 * x^1. The algorithm effectively computes these required powers of x (x^1, x^2, x^4, x^8, ...) and multiplies them into the result only when the corresponding bit in n is set.
As with other approaches, we handle negative exponents by taking the reciprocal of x and making the exponent positive. Using a long for the exponent is crucial to avoid overflow with Integer.MIN_VALUE.
public class Solution { public double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } double ans = 1.0; double current_product = x; for (long i = N; i > 0; i /= 2) { if ((i % 2) == 1) { ans = ans * current_product; } current_product = current_product * current_product; } return ans; }}Complexity
Time
O(log n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(log n).
Optimal space complexity of O(1) as it avoids recursion.
Most efficient and robust solution for this problem.
Cons
The logic might be slightly less intuitive to grasp initially compared to the simple loop or the direct recursive translation.
Solutions
Solution
public class Solution { public double MyPow(double x, int n) { return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long) n); } private double qpow(double a, long n) { double ans = 1; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans *= a; } a *= a; } return ans; }}class Solution {public double myPow(double x, int n) { return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long)n); }private double qpow(double a, long n) { double ans = 1; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans = ans * a; } a = a * a; } return ans; }}/** * @param {number} x * @param {number} n * @return {number} */ var myPow = function (x, n) { const qpow = (a, n) => { let ans = 1; for (; n; n >>>= 1) { if (n & 1) { ans *= a; } a *= a; } return ans; }; return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n); };class Solution {public: double myPow(double x, int n) { auto qpow = [](double a, long long n) { double ans = 1; for (; n; n >>= 1) { if (n & 1) { ans *= a; } a *= a; } return ans; }; return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long)n); }};class Solution : def myPow ( self , x : float , n : int ) -> float : def qpow ( a : float , n : int ) -> float : ans = 1 while n : if n & 1 : ans *= a a *= a n >>= 1 return ans return qpow ( x , n ) if n >= 0 else 1 / qpow ( x , - n )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.