Leetcode 50: Pow(x, n)

This problem solution relies on binary exponentiation. The key insight is that
2^10 = 2^5 * 2^5
2^5 = 2^2 * 2^2 * 2
So we can base our solution on recursively solving pow(x, n/2) and multiplying it by itself to get our result. If n is odd then we have to do an extra multiplication of x. Base case is n == 0, which results in 1. Be careful not to repeatedly call the recursive function twice as that will result in O(n) time. For O(log n) time we remember the result of pow(x, n/2) and then multiply it by itself once recursion has unravelled.

A few fiddly edge cases like dealing with negative exponents, where we can just return 1.0 / pow(x, -n). The most tricky edge case is INT_MIN, which would overflow if we negate it. So instead I add one to the exponent, deal with that and then multiply it by the remaining x.

There is also an iterative solution but I find that less intuitive. Here are my whiteboard notes for the iterative solution:

And here is the c++ source code is here:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *