Click here to go back to LeetCode summary page.
Problem description is here, or as follows:
Implement pow(x, n).
While, technically, a naive approach like mutiply x by n times does the job (run-time complexity of O(N)), it is not very efficient if n is very large. More efficient way with O(log(N)) best case and O((log(N))^2) worst case run-time complexity starts with decompose n to the sum of 2^(2^(k-1)) series (with k>=1), while k is an integer. The idea is to let the product rolls itself over exponentially rather than linearly. For example, if n is 23, then it can be decomposed to
so that the total number of multiplication operations to get the result is (4+2+1+0) +3 = 10 (the additional 3 is needed to multiply four terms together).
Again, several situations needed to consider:
See the code for details. This algorithm is a common approach to implement some advanced numerical computation. Another example is “Divide Two Integers” problem.