Easy

Quiz

#292 Nim Game

APPROACH

You and a friend take turns removing 1 to 3 stones from a pile, with you going first. The player who removes the last stone wins.

The pile starts with n stones. Return true if you can guarantee a win with optimal play, or false if your opponent can guarantee a win.

Example 1:

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:

Input: n = 1

Output: true

Example 3:

Input: n = 2

Output: true

1 of 4

1:00

What is the optimal approach for this problem?