Question: https://oj.leetcode.com/problems/powx-n/
Question Name: Pow(x, n)
The simplest solution is to use the build-in function “pow” or build-in operation “**” of Python.
1 2 3 4 5 6 | class Solution: # @param x, a float # @param n, a integer # @return a float def pow(self, x, n): return x**n |
A second simple solution is recursive.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: # @param x, a float # @param n, a integer # @return a float def pow(self, x, n): if n == 0: return 1 # Handle with special case elif n < 0: return 1.0 / self.pow(x, -n) # Handle with negative n elif n == 1: return x # Termination condition else: # Recursive condition if n % 2 == 0: return self.pow(x*x, n//2) else: return self.pow(x*x, n//2)*x |
Finally, a iterative solution works here.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution: # @param x, a float # @param n, a integer # @return a float def pow(self, x, n): if n == 0: return 1 if n < 0: div = True; n = -n else: div = False stack = [] while n != 1 and n != -1: if n % 2 == 0: stack.append(1) else: stack.append(x) n //= 2 result = x while len(stack) != 0: result = result * result * stack.pop() if div: return 1.0 / result else: return result |