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.