LeetCode 50. Pow(x, n)

Description

https://leetcode.com/problems/longest-increasing-subsequence/

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−2³¹, 2³¹ − 1]

Explanation

break into base case where n = 0 or n = 1 and recurrent relations where n is even or odd numbers.

Python Solution

class Solution:
    def myPow(self, x: float, n: int) -> float:
        return self.helper(x, n)
    
    def helper(self, x, n):        
        if n == 0:
            return 1

        if n < 0:
            return 1 / (self.helper(x, -n))
        
        if n == 1:
            return x

        if n > 1:
            if n % 2 == 0:
                return self.helper(x * x, n // 2)                
            else:
                return x * self.helper(x * x, n // 2)

• Time complexity: ~log(N)
• Space complexity: ~1