MemoryError in the Nim Sum game on Leetcode

Question

I'm trying to solve the following problem from https://leetcode.com/problems/nim-game/description/:

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

I came up with the following solution, using a bottom-up dynamic programming approach:

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 3:
            return True
        win = [None for _ in range(n+1)]
        win[1] = win[2] = win[3] = True
        for n in range(4, n+1):
            win[n] = not all([win[n-i] for i in [1, 2 ,3]])
        return win[n]

However, when I try to submit this, I get a MemoryError:

Since the exact test case for which this MemoryError arises is not given, I'm struggling to see what is causing the problem. Any ideas?

You assume you can hold in memory the solution for every game up to and including n. This being a competitive site (I assume), they're not going to give you small numbers like a million. — Kenny Ostrom
Instead of generating the solution for every game up to n maybe you could try to generate one for let's say up to 20, examine it and see if you can spot a pattern. If there's one you could exploit it to generate solution for n without having to generate all the other solutions up to n-1. — niemmi

Kurt Peek Kurt Peek · Accepted Answer · 2017-09-03T16:34:33

Indeed as pointed out by Kenny Ostrom, probably the test cases are for such large n that there is insufficient memory to store the answers generated in the 'bottom up' dynamic programming approach. By running it on a smaller example, I noticed that the answer is simply

bool(x % 4)

MemoryError in the Nim Sum game on Leetcode

1 Answers