1510. Stone Game IV LeetCode Solution

In this guide, you will get 1510. Stone Game IV LeetCode Solution with the best time and space complexity. The solution to Stone Game IV problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Stone Game IV solution in C++
Stone Game IV solution in Java
Stone Game IV solution in Python
Additional Resources

1510. Stone Game IV LeetCode Solution image

Problem Statement of 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).

Constraints:

1 <= n <= 105

Complexity Analysis

Time Complexity: O(n^{1.5})
Space Complexity: O(n)

1510. Stone Game IV LeetCode Solution in C++

class Solution {
 public:
  bool winnerSquareGame(int n) {
    // dp[i] := the winning result for n = i
    vector<bool> dp(n + 1);

    for (int i = 1; i <= n; ++i)
      for (int j = 1; j * j <= i; ++j)
        if (!dp[i - j * j]) {  // Removing j^2 stones make the opponent lose.
          dp[i] = true;        // So, we win.
          break;
        }

    return dp[n];
  }
};
/* code provided by PROGIEZ */

1510. Stone Game IV LeetCode Solution in Java

class Solution {
  public boolean winnerSquareGame(int n) {
    // dp[i] := the winning result for n = i
    boolean[] dp = new boolean[n + 1];

    for (int i = 1; i <= n; ++i)
      for (int j = 1; j * j <= i; ++j)
        if (!dp[i - j * j]) { // Removing j^2 stones make the opponent lose.
          dp[i] = true;       // So, we win.
          break;
        }

    return dp[n];
  }
}
// code provided by PROGIEZ