23.05.04 Today’s Leetcode

649. Dota2 Senate (medium)

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        rQ = deque()
        dQ = deque()
        
        for i,c in enumerate(senate):
            if c == "R":
                rQ.append(i)
            else:
                dQ.append(i)
        while dQ and rQ:
            d,r = dQ.popleft(), rQ.popleft()
            if d < r:
                dQ.append(d + len(senate))
            else:
                rQ.append(r + len(senate))

        return "Radiant" if rQ else "Dire"

650. 2 Keys Keyboard (medium)

DFS Approach

class Solution:
    def minSteps(self, n: int) -> int:

        dp = {}
        dp[n] = 0

        def dfs(cur, copy):
            if cur == n: return 0
            if cur > n: return math.inf
            temp = math.inf
            if copy != cur: temp = min(temp, dfs(cur, cur))
            if copy > 0: temp = min(temp, dfs(cur + copy, copy))
            return temp + 1

        return dfs(1, 0)
            

Mathematical Approach

class Solution:
    def minSteps(self, n: int) -> int:
        factorization = []
        d = 2
        while n > 1:
            while n % d == 0:
                factorization.append(d)
                n = n // d
            d += 1
        return sum(factorization)

991. Broken Calculator (medium)

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:

        moves = 0

        while target > startValue:
            if target % 2 == 0:
                target //= 2
            else:
                target += 1

            moves += 1
        
        if target < startValue:
            moves += (startValue - target)

        return moves