23.07.24 Today’s Leetcode

50. Pow(x, n)

with DFS

class Solution:
    def myPow(self, x: float, n: int) -> float:

        def bs(x, n):
            if x == 0: return 0
            if n == 0: return 1

            res = bs(x, n // 2)
            res = res * res
            if n % 2:
                return res * x
            else: 
                return res


        res = bs(x, abs(n)) 
        if n >= 0: 
            return res
        return 1 / res

2550. Count Collisions of Monkeys on a Polygon (medium)

TLE with O(n)

class Solution:
    def monkeyMove(self, n: int) -> int:
        
        cur = 0
        res = 0
        for i in range(3, n + 1):
            cur = res + i * 2
            res = cur

        return cur % (10 ** 9 + 7)

Bitmask Solution [https://leetcode.com/problems/count-collisions-of-monkeys-on-a-polygon/solutions/3111623/very-clear-explanation-straightforward-solution-explanation-case-missed/]
think easy, 2**n - 2

class Solution:
    def monkeyMove(self, n: int) -> int:
        modulo = 1_000_000_007
        answer = 1
        exponent = 2
        while n:
            if n & 1:
                answer *= exponent                
            exponent = (exponent*exponent) % modulo
            n >>= 1
        answer += modulo - 2
        answer %= modulo      
        return answer