35
LeetCode Explained: 50. Pow(x, n) - Logarithmic Exponentiation (medium)
The task of the problem at hand is quite clear: implement an exponentiation function, pow(x, n), that raises x to the power of n (n is an integer). Original link here.
Constraints:
Example 1:
Example 2:
It is obvious that we can of course multiply the number x by itself n times (and in the case of n being negative, multiply 1/x by itself the corresponding number of times). This approach takes O(n) time and is not the fastest one.
And then:

We can then calculate x to the power of n by calculating x^2, then x^4 (by multiplying x^2 by itself) and so forth, until we get to x^n.
The algorithm looks like this:
- if we find an odd n, we multiply a by x.
- we multiply x by itself and store the result in x.
- we divide n by 2 and store the result in n.
For this approach to factorisation, we have to perform log n operations. If n doubles, then the operations performed only grow by 1, as opposed to the first approach, in which the number of operations performed will double if n doubles.
This is a very basic implementation of the algorithm:
This approach is called logarithmic exponentiation and an examples where it proves useful is computing recurrence relations. I provided a more detailed description of the matter in this article I wrote some time ago, which explains how to compute Fibonacci numbers using fast matrix exponentiation.
That concludes today's solution. I'll be back with other LeetCode solutions (including harder ones!) for the LeetCode Explained series, so don't forget to subscribe!
35