Nim Game

Problem

You are playing the following Nim Game with your friend:

• Initially, there is a heap of stones on the table.
• You and your friend will alternate taking turns, and you go first.
• On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
• The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

Examples

Example 1:

1
2
3
4
5
6
7

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:

1
2

Input: n = 1
Output: true

Example 3:

1
2

Input: n = 2
Output: true

Solution

Method 1 - DFS

Assume we have n stones, then I can pick up 1, 2 or 3 stones - and my friend can now play with n-1, n-2 and n-3 stones.

Because I am playing first, my friend has to win in all the cases i.e.:

1

friendWin = f(n - 1) && f(n - 2) && f(n - 3)

If he doesn’t win in any of the case, that means i have possibility of winning and hence I will play that move.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

boolean canWinNim(int n) {

	if (n <= 3) {
		return true;
	}

	if (n == 4) {
		return false;
	}
	//I can choose a solution to make my friend fail
	boolean friendWin = canWinNim(n - 1) && canWinNim(n - 2) && canWinNim(n - 3);
	//my friend fail == my win
	return !friendWin;
}

Method 2 - DP

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

boolean canWinNim(int n) {
	Map<Integer, Boolean> ans = new HashMap<>();
	int i = 1;

	while (i <= n) {
		if (i <= 3) {
			ans.put(i, true);
			i++;
			continue;
		}

		if (i == 4) {
			ans.put(i, false);
			i++;
			continue;
		}
		// find one solution that let friend fail after a choose
		boolean counter = ans.get(i - 1) && ans.get(i - 2) && ans.get(i - 3);
		ans.put(i, !counter);
		i++;
	}

	return ans.get(n);
}

Method 3 - Observation

The crucial insight is that the game strategy revolves around multiples of 4.

Here is the key observation:

• If the number of stones ( n ) is a multiple of 4, you will always lose if both players play optimally. This is because if ( n ) is a multiple of 4, no matter how many stones you take (1, 2, or 3), you will always leave a multiple of 4 for your friend to take on their turn. Thus, your friend can always adjust their moves to leave you a multiple of 4, and you’ll lose eventually.
• If ( n ) is not a multiple of 4, you can always adjust your move to leave a multiple of 4 for your friend. This way, you can force a win.

Now, lets look at some games for n:

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, this is how the game play out for n:

Code

1
2
3

public boolean canWinNim(int n) {
	return n % 4 != 0
}