[LeetCode] 050. Pow(x, n)
-
date_range April 04, 2019 - Thursday info
Problem (Medium)
Implement pow(x, n)
, which calculates x
raised to the power n (x^n).
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^31, 2^31 − 1]
Approach 1: (My Solution 41.86%) Use the Binary of n
Idea
The purpose of this problem to try to find better ways to save computation in the possible multplication loops. My strategy:
- Convert the
n
to binary. e.g. n=10 ->0b1010
; - Thus,
pow(2, 10)
equals to(2x2)^3 * (2x2)^1
;
Solution
class Solution1:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
def square(x, n):
res = x
while(n):
res = res*res
n -= 1
return res
res = 1.0
for i, c in enumerate(bin(abs(n))[-1:1:-1]):
if c == '1':
res *= square(x, i)
if n < 0:
return 1 / res
return res
Complexity
- Time: $O()$?
- Space: $O()$?
KF