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.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ