Leetcode Problem: "pow(x, n)"

Hello everyone,

Sorry for the long wait for this post; recently I started helping my C++ professor debug a few labs and I was having issues of my own with today's problem. Today we will be going over the "pow(x, n)" Leetcode problem. This problem is a medium difficulty problem, though the description makes it seem it is simpler than what it actually is. At the end of the post I have attached my solution code for this problem. Without further ado, lets get right into this!

pow(x, n)

From the prompt and what we know about exponents, we know a few things:

1. The range of x
2. n is an integer and its range
3. Things about exponents
1. x raised to 0 gives us 1
2. x raised to 1 gives us x
3. x raised to -1 gives us (1 / x)

One important thing to remember is that n could be the maximum or minimum number in its range.

Solution

The first solution that I started out was a "loop" solution. I have an if-else chain that covers the basics of powers (like x^0 = 1) and executes the correct for-loop depending on if n was positive or negative. If n was positive, the for-loop will calculate the power by multiplying the base, x, by itself n times. If n was negative, the for-loop will calculate the power of the denominator first, then return (1 / denominator) because 1 to the power of anything is always 1 (see code).

However, I ran into a time limit issue:

My code was too slow to pass test cases involving large exponents. The reason for it is that the loops causes the worst-case time complexity to be O(n), where n is dependent on the exponent. Since n, in this test case, was set to the maximum number in its range, it will take a while to calculate.

I ended up looking up the worst-case time complexity that I must achieve for my implementation of pow(x, n). The prompt did not state the speed I should aim for, so I researched into the ideal time complexity for pow(x, n).

One post I saw on StackOverflow stated that pow(x, n) needed a constant time complexity:

However, the solution for this (as shown above) is currently out of the realm of what I know so far. Mainly because of I do not know how 2 XOR (y*log2(x)) gives the correct results.

After digging a little further, I ended up using a solution given by geeksforgeeks.org:

This solution uses recursion to do the power calculations. This solution is O(log N) because we are dividing the problem by (y / 2) with each call to power(x, y). At first I was wondering how this solution could work, until I remember that we can split powers and still get the same result.

x^n = x^(n / 2) * x^(n / 2) = x^(n / 4) * x^(n / 4) * x^(n / 4) * x^(n / 4) = … (when n is even)

x^n = x * x^(n / 2) * x^(n / 2) = x * x^(n / 4) * x^(n / 4) * x^(n / 4) * x^(n / 4) = … (when n is odd)

I did not use the exact code as shown above, as this code takes into account the fact that y can be positive or negative. In my solution, it firsts makes the necessary checks in myPow(x, n), then calls myPowRecur(x, n) when needed. myPowRecur(x, n) assumes n will be a positive integer because myPow(x, n) makes n positive before calling myPowRecur(x, n) when n is negative.

Results

After a few bug fixes and tests, I manage to pass Leetcode's tests:

Run time is pretty low due to the O(log N) recursive solution. The memory usage comes from our use of variables and the recursive method calls on the stack.

Conclusion

Overall, this was a pretty hard problem to solve. When I first saw the "medium" difficulty rating after reading the prompt, I though this problem should have been rated as "easy". However, I soon saw that this was no easy problem, especially since I took the geeksforgeeks.org solution and modified it to my means. Nevertheless, it was quite enjoyable to solve and such. I will be working on another Leetcode problem soon. Thank you for reading and I will see you next time!

Link to source: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Pow(x%2C%20n).cpp