[LeetCode] Pow(x, n)

leetcode

This problem ask us to implement the power function.
As the first thought, we may think it’s easy to use a recursive function or a loop.
Like x^n = x * x^(n-1)
However, it’s O(n) time and may encounter LTE for being too slow.
Our ideal time complexity is O(logn) instead of O(n).

In fact, for x^n, we can divide it into x^(n/2) * x^(n/2)
so that we can reach logn time.
For this solution, all we need to worry about is odd numbers which cannot be divided by 2.
Let’s take x^7 as an example. We can take separate it into x * x^3 * x^3.
That is to say, for odd numbers, all we need to do is calculate x//2 and times one more time x.

We also need to handle unusual cases like negative power.
Fortunately, we can just calculate it by return the reciprocal of itself.

Let’s look at the code. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    """
    @param: x: the base number
    @param: n: the power number
    @return: the result
    """
    def myPow(self, x, n):
        # write your code here

        def power(x, n):
            if n == 0: return 1
            half = power(x, n // 2)
            if n % 2 == 0: return half * half
            return x * half * half

        if n < 0: return 1/power(x, -n)
        return power(x, n)