Leetcode – Nim Game

Tags:

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.

Hint:

  1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Analysis

A native method is to use deep first search. The basic ideas can be expressed as:

We can make the above program faster using dynamic programming.

The above solutions can not work for large n. It turned out that, the first player will loose only when n % 4 == 0.

  1. n = 1, 2, 3, the first player wins
  2. n == 4, the first play looses no matter what he will choose, his friend will have n <=3, win!
  3. n == 5, the first player can pick 1, thus leave his friend with 4, the friend will loose!
  4. n == 6, the first player can pick 2, thus leave his friend with 4. 
  5. n == 7, the first player can pick 3, thus leave his friend with 7.
  6. n == 8, the first player will leave his friend with 7, 6 or 5.  So his friend will win!
  7. n == 9, the first player will pick 1, so leave his friend with 8, his friend will loose.

So the final solution can be easily implemented in Java as follows: