/292. Nim Game

292. Nim Game

Easy
Probability59.3% acceptance

Given an integer heap_size representing the number of stones in a heap, determine whether the first player can win the game assuming both players play optimally. On each turn, a player removes 1, 2, or 3 stones from the heap. The player who removes the last stone wins. Return True if the first player can guarantee a win, otherwise return False.

Example 1

Input: heap_size=5

Output: True

Explanation: First player removes 1 stone, leaving 4. Second player cannot win from 4.

Example 2

Input: heap_size=8

Output: False

Explanation: First player cannot avoid leaving a heap of 4 after their turn, so second player wins.

Constraints

  • 1 <= heap_size <= 231 - 1
Python (current runtime)

Case 1

Input: heap_size=7

Expected: True

Case 2

Input: heap_size=12

Expected: False

Case 3

Input: heap_size=15

Expected: True

Case 4

Input: heap_size=20

Expected: False