Fast and consise solution via using bitmask


  • 0
    W
    class Solution(object):
        def canIWin(self, maxInt, total):
            def helper(bitmask, vis, n, total):
                if total <= 0:
                    return False
                if bitmask in vis:
                    return vis[bitmask]
                for i in xrange(n - 1, -1, -1):
                    bit = 2 << i
                    if bitmask & bit == 0 and not helper(bitmask | bit, vis, n, total - i - 1):
                        vis[bitmask] = True
                        return True
                vis[bitmask] = False
                return False
            if total == 0: 
                return True
            if (1 + maxInt) * maxInt / 2 < total:
                return False
            return helper(0, {}, maxInt, total)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.