Move-to-Zero Turn Game (Steps 1, 2, or x)

Reported in interviews at Jump Trading

Problem statement

Two players play a game starting from a positive integer position n. They alternate turns; on a turn the current player decreases the position by exactly 1, 2, or x (a fixed move size given as input), but only by a move that keeps the position >= 0. The player who moves the position to exactly 0 WINS. Player 1 moves first.

Return True if Player 1 (the first player) has a winning strategy from position n, else False.

Complete:

first_player_wins(n: int, x: int) -> bool

Constraints: n >= 0, x >= 1. If n == 0 the game is already over before Player 1 moves, so Player 1 cannot make the winning move -> False. Example: n = 1, x = 3: Player 1 subtracts 1, reaching 0, and wins -> True. By contrast n = 3, x = 4 is a loss for Player 1 -> False: the only legal moves from 3 (subtract 1 to 2, or 2 to 1; 4 is too large) both hand the opponent a winning position.

Show hint

Which positions can you label as won or lost without any search, and how do those labels propagate upward?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems