Can I Win
Intuition
Solution
class Solution:
def canIWin(self, n: int, total: int) -> bool:
if (1 + n) * n // 2 < total:
return False
nums = 2 ** n - 1
self.cache = [None] * (nums + 1)
return self._helper(nums, total)
def _helper(self, nums, desired):
if self.cache[nums] is not None:
return self.cache[nums]
i = 1
current = 1
while i <= nums:
if not i & nums:
pass
elif current >= desired:
self.cache[nums] = True
return True
elif not self._helper(nums ^ i, desired - current):
self.cache[nums] = True
return True
i = i << 1
current += 1
self.cache[nums] = False
return False