50. Pow(x, n)[M]

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

Description

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

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
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 [−231, 231 − 1

Solution

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

https://leetcode.com/discuss/93413/iterative-log-n-solution-with-clear-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 9 = 2^3 + 2^0 = 1001
        # x^9 = x^(2^3)*x(2^0)
        # multiple x^i when i place is 1
        if n == 0:
            return 1
        res ,curr = 1, abs(n)
        while curr > 0:
            if curr & 1 == 1:
                res *= x
            curr >>= 1
            x *= x
        if n < 0:
            return 1 / res
        return  res

231. Power of Two[E]

https://leetcode.com/problems/power-of-two/

Description

Given an integer, write a function to determine if it is a power of two.

Example 1:

1
2
3
Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

1
2
3
Input: 16
Output: true
Explanation: 24 = 16

Example 3:

1
2
Input: 218
Output: false

Solution

1
2
3
4
5
6
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n < 0:
            return False
        bin_str = bin(n)
        return sum(map(lambda x: int(x), list(bin_str[2:]))) == 1

326. Power of Three[E]

https://leetcode.com/problems/power-of-three/

Description

Given an integer, write a function to determine if it is a power of three.

Example 1:

1
2
Input: 27
Output: true

Example 2:

1
2
Input: 0
Output: false

Example 3:

1
2
Input: 9
Output: true

Example 4:

1
2
Input: 45
Output: false

Follow up:
Could you do it without using any loop / recursion?

Solution

https://leetcode.com/problems/power-of-three/solution/

1
2
3
4
5
6
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        max3pow = 1162261467
        if n <= 0 or n > max3pow:
            return False
        return max3pow % n == 0

342. Power of Four[E]

https://leetcode.com/problems/power-of-four/

Description

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

1
2
Input: 16
Output: true

Example 2:

1
2
Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

Solution

1
2
3
4
5
6
7
class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        # bin(4**0) '0b1'
        # bin(4**1) '0b100'
        # bin(4**2) '0b10000'
        # bin(4**3) '0b1000000'
        return num > 0 and num & (num-1) == 0 and len(bin(num)[3:]) % 2 == 0

372. Super Pow[M]

https://leetcode.com/problems/super-pow/

Description

Your task is to calculate a**b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

1
2
Input: a = 2, b = [3]
Output: 8

Example 2:

1
2
Input: a = 2, b = [1,0]
Output: 1024

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def __init__(self):
        self.base = 1337

    def superPow(self, a: int, b: List[int]) -> int:
        # One knowledge: ab % k = (a%k)(b%k)%k
        # a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k
        if b is None or len(b) == 0:
            return 1
        last_digit = b.pop()
        return self.powmod(self.superPow(a, b), 10) * \
            self.powmod(a, last_digit) % self.base

    def powmod(self, a, k):
        a %= self.base
        result = 1
        for i in range(k):
            result = (result * a) % self.base
        return result