Stone Game IV
Hard · Dynamic Programming · Math · Dynamic Programming · Game Theory
Problem
Alice and Bob take turns, Alice first. A pile starts with n stones. On a turn the player removes a non-zero perfect square number of stones (1, 4, 9, ...). A player who cannot move loses.
Assuming both play optimally, return true if Alice wins, otherwise false.
Examples
Input: n = 5 Output: false
Alice can leave 4 or 1, and Bob then takes everything.
Input: n = 6 Output: true
Alice takes 1 and leaves 5, a losing count for Bob.
Input: n = 7 Output: false
Alice can leave 6 or 3, and Bob wins from both.
Constraints
- 1 <= n <= 10^5
Approaches
- Pull: try every square from each count — time O(n·√n), space O(n)
Follow-up
Losing counts are sparse: below 10^5 there are fewer than 3,000 of them (0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, ...). That is why pushing from them is fast. The use cases replace the squares by any move list, and flip the rule so that taking the last stone loses.
Related problems
Start free on Cariara · Coding problems · System design studio
