LC-0050 Medium LeetCode

50. Pow(x, n)

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 37% Topics: Math, Recursion

Reading material

Math & Geometry 12 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(logn)
# Space: O(1)

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        result = 1
        abs_n = abs(n)
        while abs_n:
            if abs_n & 1:
                result *= x
            abs_n >>= 1
            x *= x

        return 1 / result if n < 0 else result


# Time:  O(logn)
# Space: O(logn)
# Recursive solution.
class Solution2(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0 and n != -n:
            return 1.0 / self.myPow(x, -n)
        if n == 0:
            return 1
        v = self.myPow(x, n / 2)
        if n % 2 == 0:
            return v * v
        else:
            return v * v * x

Solution from kamyu104/LeetCode-Solutions · MIT