powx_n

 1# @leet start
 2class Solution:
 3    def myPow(self, x: float, n: int) -> float:
 4        r"""
 5        This function calculates the power of a number to another number in Log(n) time.
 6
 7        To do this in linear time, we simply turn $x ^ n$ into x * n (n times).
 8
 9        Since we have to do this in linear time, we have to take a max of log(n) operations.
10
11        We can do this by recursively taking the n multiplications and dividing them by two.
12
13        This works because, imagine (2 ^ 4), which is 16. This can be reduced to 4 * 4.
14        Or $(2 * n / 2) * (2 * n / 2)$. To generalize this, x ^ n, where n is even becomes:
15
16        $$
17        (x * n / 2) * (x * n / 2).
18        $$
19
20        For an odd power, we can't evenly divide the powers. Imagine we have to calculate
21        2 ^ 5. We can't divide this in half cleanly.
22
23        However, this can be reduced to (2 * 2) * (2 * 2) * 2, since we know that x ^ n
24        is equal to x ^ (n - 1) * x.
25        So for the odd case, we floor divide the power by 2 and then multiply it by x as well.
26
27        We do this recursively and define the two base cases, which are when n = 1 and n = 0.
28        When n = 0, we always return 1.
29        When n = 1, we return x.
30        When n % 2 == 0, we return $pow(x * x, n // 2)$.
31        When n % 2 == 1, we return $pow(x * x, n // 2) * x$.
32        If n is negative, simply return $1 / pow(x, -n)$ (the inverse).
33
34        For $2 ^ 8$: Note there are only 3 multiplications.
35        ```mermaid
36        graph TB;
37            A((2 ^ 8))-->B((4 ^ 4))
38            B-->C((16 ^ 2))
39            C-->D((256))
40        ```
41
42        For $2 ^ 9$: Note there are only 4 multiplications.
43        ```mermaid
44        graph TB;
45            A((2 ^ 9))-->B((4 ^ 4))
46            A-->E((2))
47            B-->C((16 ^ 2))
48            C-->D((256))
49        ```
50        """
51        if n < 0:
52            return 1 / self.myPow(x, -n)
53        if n == 0:
54            return 1
55        if n == 1:
56            return x
57        if n % 2 == 0:
58            return self.myPow(x * x, n // 2)
59        if n % 2 == 1:
60            return x * self.myPow(x * x, (n - 1) // 2)
61        return 0
62
63
64# @leet end
65sol = Solution()
66
67
68def test_even_pow():
69    """Test the path where the pow is positive and even."""
70    assert sol.myPow(2, 4) == 16
71
72
73def test_odd_pow():
74    """Test the path where the pow is positive and odd."""
75    assert sol.myPow(2, 5) == 32
76
77
78def test_zero():
79    """Test the path where the pow is 0."""
80    assert sol.myPow(2, 0) == 1
81
82
83def test_pow_one():
84    """Test the path where the pow is 1."""
85    assert sol.myPow(2, 1) == 2
86
87
88def test_negative_even():
89    """Test the path where the pow is negative and even."""
90    assert sol.myPow(2, -2) == 1 / 4
91
92
93def test_negative_odd():
94    """Test the path where the pow is negative and odd."""
95    assert sol.myPow(2, -3) == 1 / 8