LC-0464 Medium LeetCode

464. Can I Win

Math Dynamic Programming Bit Manipulation Memoization Game Theory Bitmask

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 30% Topics: Math, Dynamic Programming, Bit Manipulation, Memoization, Game Theory, Bitmask

View full problem on LeetCode

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n!)
# Space: O(n)

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        def canIWinHelper(maxChoosableInteger, desiredTotal, visited, lookup):
            if visited in lookup:
                return lookup[visited]

            mask = 1
            for i in xrange(maxChoosableInteger):
                if visited & mask == 0:
                    if i + 1 >= desiredTotal or \
                       not canIWinHelper(maxChoosableInteger, desiredTotal - (i + 1), visited | mask, lookup):
                        lookup[visited] = True
                        return True
                mask <<= 1
            lookup[visited] = False
            return False

        if (1 + maxChoosableInteger) * (maxChoosableInteger / 2) < desiredTotal:
            return False

        return canIWinHelper(maxChoosableInteger, desiredTotal, 0, {})

Solution from kamyu104/LeetCode-Solutions · MIT