#1510
Stone Game IV
expert · 1190 · lc hard +32 · verified · 59.6% accepted · 1,640 likes · top 57%
Description
Alice goes first in a two-player stone game. There are n stones; each turn a player removes a positive perfect-square number of stones. A player who cannot move loses. Given n, return true if Alice wins with optimal play, or false if Bob wins.
Example 1:
Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Example 2:
Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Example 3:
Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Code
1
2
3