Python solution with detailed explanation


  • 0
    G

    Solution

    Nim Game https://leetcode.com/problems/nim-game/

    Dynamic Programming Solution

    • Just maintain the last three outcomes.
    class Solution(object):
        def canWinNim(self, n):
            """
            :type n: int
            :rtype: bool
            """
            if n <= 3:
                return True
            win = [True]*3
            i = 4
            while i <= n:
                next_outcome = (not win[0]) or (not win[1]) or (not win[2])
                win[0] = win[1]
                win[1] = win[2]
                win[2] = next_outcome
                i = i + 1
            return win[-1]
    

    Mathematical Answer

    • Multiple of 4 will always result in loss.
    class Solution(object):
        def canWinNim(self, n):
            """
            :type n: int
            :rtype: bool
            """
            return False if int(n % 4) == 0 else True
    

Log in to reply
 

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