Leetcode 50. Pow(x, n)
Problem Explanation
The problem is asking us to implement the pow function i.e. given inputs x
and n
, where x
is a base and n
is an exponent, calculate x
raised to the power n
(x^n). The base number x
is a floating point number and it lies between -100 and 100, while the exponent n
is a 32-bit signed integer which is in range [-2^31, 2^31 - 1].
To better understand this, let's take a look at an example.
If we take the inputs as x
=2.00000 and n
=10, the output will be 2^10 = 1024.00000
Solution Approach
The solution uses a standard technique called "exponentiation by squaring" to efficiently calculate the power of a number. This is a more efficient approach than performing n
multiplication operations.
In case the power n
is negative, we calculate the positive power of the number and then take the reciprocal of it as x^-n = 1/(x^n)
If the power n
is even, we use the property x^(2n) = (x^2)^n
to half the number of multiplication operations by calculating x*x
and reducing n
by half.
If n
is odd, we multiply the result by x
and reduce n
by 1 to make it even.
We continue these steps until n
is reduced to 0, at which point we return 1 (since any number raised to the power 0 is 1).
Python Solution
1 2python 3class Solution: 4 def myPow(self, x: float, n: int) -> float: 5 if n == 0: 6 return 1.0 7 if n < 0: 8 return 1 / self.myPow(x, -n) 9 if n % 2: 10 return x * self.myPow(x, n - 1) 11 return self.myPow(x * x, n // 2)
Java Solution
1
2java
3public class Solution {
4 public double myPow(double x, long n) {
5 if(n == 0)
6 return 1.0;
7 if(n < 0)
8 return 1 / myPow(x, -n);
9 if(n % 2 == 1)
10 return x * myPow(x, n - 1);
11 return myPow(x * x, n / 2);
12 }
13}
Javascript Solution
1
2javascript
3var myPow = function(x, n) {
4 if(n === 0)
5 return 1.0;
6 if(n < 0)
7 return 1 / myPow(x, -n);
8 if(n % 2 === 1)
9 return x * myPow(x, n - 1);
10 return myPow(x * x, Math.floor(n / 2));
11};
C++ Solution
1
2cpp
3class Solution {
4public:
5 double myPow(double x, long n) {
6 if(n == 0)
7 return 1.0;
8 if(n < 0)
9 return 1 / myPow(x, -n);
10 if(n % 2 == 1)
11 return x * myPow(x, n - 1);
12 return myPow(x * x, n / 2);
13 }
14};
C# Solution
1
2csharp
3public class Solution {
4 public double MyPow(double x, long n) {
5 if(n == 0)
6 return 1.0;
7 if(n < 0)
8 return 1 / MyPow(x, -n);
9 if(n % 2 == 1)
10 return x * MyPow(x, n - 1);
11 return MyPow(x * x, n / 2);
12 }
13}
Here, the myPow
function is recursively calling itself with updated values of x
and n
until n
is zero. At each step, based on whether n
is odd or even, it either halves n
and squares x
or decrements n
by 1 and multiplies x
with the returned value of the recursive call.
The described solutions for Python, Java, JavaScript, C++, and C# implement the recursive "exponentiation by squaring" strategy effectively but do have a small flaw- they donโt consider the mathematical rule of squaring. This could cause an overflow for larger values of n
.
To circumvent this issue, it's necessary to rewrite recursive calls in iterative form using a loop. The updated solutions, that also handle the edge cases, would look like this:
Python Solution
1
2python
3def myPow(x, n):
4 if n < 0:
5 x = 1 / x
6 n = -n
7 pow = 1
8 while n:
9 if n & 1:
10 pow *= x
11 x *= x
12 n >>= 1
13 return pow
JavaScript Solution
1 2javascript 3var myPow = function(x, n) { 4 if (n < 0) { 5 x = 1 / x; 6 n = -n; 7 } 8 let pow = 1; 9 while (n) { 10 if (n & 1) { 11 pow *= x; 12 } 13 x *= x; 14 n >>= 1; 15 } 16 return pow; 17};
Java Solution
1 2java 3public double myPow(double x, long n) { 4 if (n < 0) { 5 x = 1 / x; 6 n = -n; 7 } 8 double pow = 1.0; 9 while (n != 0) { 10 if ((n & 1) == 1) { 11 pow *= x; 12 } 13 x *= x; 14 n >>= 1; 15 } 16 return pow; 17}
In these updated solutions, if the exponent n
is negative we first convert the base into its reciprocal and make n
positive. We then initialize pow
to 1.0, which will hold the final result. In the while loop, we look at the least significant bit of n
using the bitwise AND operator (&). If the least significant bit is 1, we multiply the current pow
by x
. We then square x
and right-shift n
by 1(bitwise operation) thus removing its least significant bit. We repeat these steps until n
becomes 0, at which point pow
holds the calculation of x
raised to the power of n
.
This way, we achieve an efficient and mathematically sound implementation of the power function.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.