Algorithm Puzzles: Pow(x, n)

Posted on Edited on In Views: Word count in article: 137 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Pow(x, n)

Puzzle

Puzzle from leetcode:

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

Solution

First came out solution

1
2
3
class Solution:
    def myPow(self, x: float, n: int) -> float:
        return x**n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    @lru_cache
    def myPow(self, x: float, n: int) -> float:
        ret = 1
        absn = abs(n)

        if absn >= 4 and absn % 2 == 0:
            half = int(n / 2)
            return self.myPow(x, half) * self.myPow(x, half)
        elif absn >= 4:
            half = int(n / 2)
            ret = self.myPow(x, half) * self.myPow(x, half)
            return ret * x if n > 0 else ret / x
        elif n > 0:
            while n > 0:
                ret = ret * x
                n = n - 1
        elif n < 0:
            while n < 0:
                ret = ret / x
                n = n + 1

        return ret

T.C. should be O(n/2)