Is Stone Game IV easy or hard?

Stone Game IV is classified as Hard on LeetCode even though the implementation is short. The difficulty comes from recognizing the game theory pattern and modeling the problem as DP with winning and losing states.

Stone Game IV Python/Java solution

Both Python and Java implementations typically use a DP array of size n+1. For each index i, iterate through j*j ≤ i and mark dp[i] true if dp[i - j*j] is false. The same logic works across languages including C++, JavaScript, and C#.

How to solve Stone Game IV in O(n)?

A strict O(n) solution is not commonly used for this problem because each state must consider multiple square moves. The standard optimal approach checks all perfect squares ≤ n for every state, resulting in O(n√n) time using dynamic programming.

What is the best approach for Stone Game IV?

Dynamic Programming is the most reliable approach. Define dp[i] as whether the current player wins with i stones. For each i, try removing every square number j*j ≤ i and check if dp[i - j*j] is false. If such a move exists, dp[i] becomes true. This runs in O(n√n) time with O(n) space.

Is Stone Game IV asked at Google/Amazon/Meta?

Stone Game style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test reasoning about game states, recursion, and dynamic programming. Variants of this problem are commonly used to evaluate understanding of optimal play strategies.

What data structure is used in Stone Game IV?

The core data structure is a boolean DP array or memoization map that stores whether a state with i stones is winning or losing. The algorithm iterates through perfect squares and performs constant-time lookups in this table.

What is the time complexity of Stone Game IV?

The optimal solution runs in O(n√n) time. For each state from 1 to n, the algorithm iterates through all square numbers up to √n. The space complexity is O(n) for storing the DP or memoization table.

Description Hints 1 Solution Video 11:06

1510. Stone Game IV

Hard65.2% acceptance1 company

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.

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).

Constraints:

1 <= n <= 10⁵

Asked at 1 company

Microsoft

Topics

Hints open one at a time

Hint 1

Use dynamic programming to keep track of winning and losing states. Given some number of stones, Alice can win if she can force Bob onto a losing state.

11:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution