50.Pow(x, n)

Tags: [divide_conquer], [trick], [math]

Com: {fb}

Link: https://leetcode.com/problems/powx-n/#/description

Implement pow(x, n).

Solution: Divide Conquer, Trick

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if not x:
            return 0

        sign = 1
        if n < 0:
            n = -n
            sign = -1

        p = self.pow_helper(x, n)
        if sign < 0:
            p = 1/p

        return p

    def pow_helper(self, x, n):
        # base case
        if n <= 0:
            return 1
        if n == 1:
            return x

        half = self.pow_helper(x, n / 2)
        if n % 2 == 1:
            return x * half * half
        else:
            return half * half

Revelation:

• Avoid overlapping computation, each time we just compute half.

Note:

• Time complexity = O(lgn), because each time n become its half.

Question:

• Why each time n become to its half, the time complexity is O(lgn)?