Terrible LeetCode in Kotlin: #50 pow(x, n)
Another day, another LeetCode question (for now). Today, I'm running through #50 pow(x, n). The problem provides a double x and an integer n, with the expected result being x^n.
The naive solution was relatively simple to implement - use either x or 1/x, and multiply 1 by that value n times. This results in a solution that runs in O(n) time and O(1) space.
However, there is a better way of accomplishing this. By using something called binary exponentiation, we can achieve O(logN) runtime and O(1) space, where n is the parameter within the function. At the core of this method is the idea that for any given exponent x^n, we are able to rewrite the function as a product of exponents x^a * x^b * ..., where a, b and all the other powers are powers of 2. With that, we can simply check the binary representation of n, and whenever there is a 1 in the 1s place, we multiply our current number with the respective power of two.
I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.
Current Grind:
Grind75 list, 22 weeks/16 hours per week, [117/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion, Naive Implementation
04:06 - Attempt at Solution Begins (Bitmask)
19:22 - Submission Discussion