Leetcode # 50. Pow(x, n)

https://leetcode.com/problems/powx-n

Solution (Memoization)

Time Complexity: O(log(n))
Space Complexity: O(log(n))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def myPow(self, x: float, n: int) -> float:
    if n == 0:
      return 1
    p = 1
    result = x  
    abs_n = abs(n)
    power_table = [x]
    while p * 2 <= abs_n:
      p *= 2
      result = result * result
      power_table.append(result) # x^(2^i)
    i = len(power_table) - 1
    power_of_2 = p
    while p < abs_n:
      if abs_n - p < (power_of_2):
        i -= 1
        power_of_2 /= 2
        continue
      p += power_of_2
      result *= power_table[i]
    return result if n > 0 else (1 / result)

Last Updated on 2023/08/16 by A1go