Math Number tricks
96. Nim Game
You and a friend play a game with one pile of n stones. You take turns, and you move first.
On each turn, the player whose turn it is removes 1, 2 or 3 stones from the pile. Nobody may skip a turn, and nobody may take more stones than the pile holds. The player who removes the last stone wins.
Both of you play perfectly: if a player has a way to force a win, they always find it. Return true if you
win the game, and false if your friend wins.
Example 1
Input: n = 7
trueExplanation: You take 3 stones and leave 4. Your friend takes 1, 2 or 3 of them, and you take whatever is left, which is the last stone.
Example 2
Input: n = 4
falseExplanation: You must take 1, 2 or 3 stones, so 3, 2 or 1 stones are left. Your friend takes them all and wins.
Example 3
Input: n = 1
trueExplanation: You take the only stone, which is the last one.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 1015
Clarifying questions
What you would ask an interviewer before writing any code.