> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/hard/stone-game-iv.md).

# Stone Game IV

## [Stone Game IV](https://leetcode.com/problems/stone-game-iv)

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

**Example 4:**

```

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).
```

**Example 5:**

```

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
```

**Constraints:**

* `1 <= n <= 10^5`

## Solutions

### 🧠 Cpp

```cpp
class Solution
{

    std::map<int, bool> cache; 
public:
    //DP solution
    //very simullar to "Climbing Stairs"
    bool winnerSquareGame(int n)
    {
        //DP cache check
        auto found = cache.find(n);
        if(found != end(cache))
            return found->second;

        //if square
        double n_sqrt = sqrt(double(n));
        if( n_sqrt - int(n_sqrt) == 0 )
            cache[n] = true;
        //iterate over all squares that we can take (all variants)
        //if there at leaest one variant where we win, we win
        else
        {
            bool i_won = false;
            vector<int> stones_to_take;
            for(int i = 1; i*i < n; ++i)
                stones_to_take.push_back(i*i);

            //start with the bigest number of stones we can take
            //and iterate down
            for(auto stone_num = rbegin(stones_to_take);
                stone_num < rend(stones_to_take);
                ++stone_num)
            {
                //check if next player lose if we take i*i stones
                if(!winnerSquareGame(n - *stone_num))
                {
                    i_won = true;
                    break;
                }
            }
            cache[n] = i_won;
        }

        return cache[n];

    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/hard/stone-game-iv.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.