338. Stone Game IV

HardDynamic Programming

Alice and Bob take turns playing a game, with **Alice starting first**. Initially, there are `n` stones in a pile. On each player's turn, that player makes a **move** consisting of **removing** any **non-zero square number** of stones in the pile. Also, if a player cannot make a move, he/she **loses** the game. Given a positive integer `n`, return `true` if and only if Alice wins the game otherwise return `false`, assuming both players play optimally.

Examples

Input: 1

Output: true

Explanation: Alice removes the single stone (1 = 1^2) and Bob has no move, so Bob loses. Alice wins.

Constraints

  • 1 <= n <= 10^5
Loading...

Run checks all cases above. Submit evaluates all test cases.