Question:
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.

Approach

Ok so the only way you can win is when it is your turn and there are 1-3 stones left. When there are 4 stones and it is your turn, you will always lose because ragardless of how many you remove, their will be 1-3 stones left for the opponent. Also remember that you always take the first turn.

A good approach to this problem is to list out examples and see if we can come up with an algorithm for determining who will win.

n stones -> win/lose
1 -> win
2 -> win
3 -> win
4 -> lose
5 -> ?

Would you win or lose when n = 5? We should try writing out what happens in the case when we take either 1, 2, or 3 stones.

If you take 1 stone:
it becomes opponents turn with n = 4 -> you win

If you take 2 stone:
it becomes opponents turn with n = 3 -> you lose

If you take 3 stone:
it becomes opponents turn with n = 2 -> you lose

Therefore you win when n = 5 since since you can take 1 stone, leaving n = 4 for your opponent. As you can see in the list above, the person who has n = 4 on their turn loses. Remember that if your opponent wins, you lose and if they lose, you win :).

Now using this approach, lets try to write out more examples.

n stones -> win/lose
1 -> win
2 -> win
3 -> win
4 -> lose
5 -> win
6 -> win
7 -> win
8 -> lose
9 -> win
10 -> win
11 -> win
12 -> lose

You may have noticed this is a type of dynamic programming where to calculate the result for n we need the result for n-1, n-2, and n-3. A player can only win when their opponent loses after taking away either 1, 2 or 3 stones.

Therefore canWin(n) = !(canWin(n-1) && canWin(n-2) && canWin(n-3)).

This equation will only return true (win) if atleast one of canWin(n-1) or canWin(n-2) or canWin(n-3) returns false (lose). Otherwise the equation returns false (lose) when all 3 return true (win).

It is quite possible you could of skipped over all that analysis if you noticed that you can only lose when n is divisible by 4. With that in mind, we just have to return true when n is not divisble by 4, which can easily be done using the modulus operator.

Solution

var canWinNim = function(n) {
    return n % 4 !== 0;
};

Alternate Solution: Recursion

Using the canWin(n) = !(canWin(n-1) && canWin(n-2) && canWin(n-3)) formula we can easily write a recursive solution.

var canWinNim = function(n) {
    if(n < 4) {
        return true;
    }
    return !(canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3));
}