Coins

Interview

Time limit1sMemory limit1024 MB

Summary

Players alternate removing 1 to 3 coins from a pile of n; whoever takes the last coin loses. Decide whether the first player wins with optimal play.

Level: Medium4 of 10
Topics: Game theory, Math, Dynamic programming, Greedy
Solved: No attempts yet

Problem

You have been challenged by the infamous magician Zhivago to his signature coin game. The game starts off with a pile of $n$ coins. You and Zhivago take turns grabbing coins from the pile, and the loser is the one who grabs the last coin. Each player must take $1$ , $2$ , or $3$ coins each turn, no more and no less.

Zhivago is a master of his own game and always plays optimally. However, you have been told that you are in a winning position and can beat Zhivago to become the coin game champion. Can you do it?

Examples1

Example 1
Input
```
2
```
Expected output
```
1
```