Leetcode 50: Pow(x, n)

A few fiddly cases of exponentiation to deal with in this problem. A simple O(n) solution is fairly straightforward but that will not pass some of the leetcode test cases. An implementation that uses binary exponentiation will work in O(log n) time and will pass the leetcode tests. One other fiddly edge case was the test case that used INT_MIN as the exponent, which does not allow us to *= -1 for negative exponents, so I had to use long int to expand the range of the exponent. My original binary exponentiation implementation was messy, so the elegant solution below took inspiration from https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/

Here are my whiteboard notes:

And here is the c++ source code:

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 *