Skip to content

Latest commit

 

History

History

1510

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

1510. Stone Game IV (Hard)

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

Companies:
Apple

Related Topics:
Math, Dynamic Programming, Game Theory

Similar Questions:

Solution 1. Bottom-up DP

Let dp[i] be whether Alice and win starting with i stones.

dp[i] = true    // If any dp[i - j * j] is false
      = false   // otherwise
      where 1 <= j * j <= i  -- the stone taken by Bob.

// OJ: https://leetcode.com/problems/stone-game-iv/
// Author: github.com/lzl124631x
// Time: O(N * sqrt(N))
// Space: O(N)
class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> dp(n + 1);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i && !dp[i]; ++j) dp[i] = !dp[i - j * j];
        }
        return dp[n];
    }
};

Some tricks for saving computation

// OJ: https://leetcode.com/problems/stone-game-iv/
// Author: github.com/lzl124631x
// Time: O(N * sqrt(N))
// Space: O(N)
class Solution {
public:
    bool winnerSquareGame(int n) {
        static vector<bool> dp(1);
        for (int i = dp.size(); i <= n; ++i) {
            dp.push_back(false);
            for (int j = 1; j * j <= i && !dp[i]; ++j) dp[i] = !dp[i - j * j];
        }
        return dp[n];
    }
};

Or

// OJ: https://leetcode.com/problems/stone-game-iv/
// Author: github.com/lzl124631x
// Time: O(N * sqrt(N))
// Space: O(N)
int dp[100001] = {[0] = 0, [1 ... 100000] = -1}, last = 0;
class Solution {
public:
    bool winnerSquareGame(int n) {
        for (int i = last + 1; i <= n; ++i) {
            for (int j = 1; j * j <= i && dp[i] != 1; ++j) dp[i] = !dp[i - j * j];
        }
        last = max(last, n);
        return dp[n];
    }
};

Solution 2. Top-down DP

// OJ: https://leetcode.com/problems/stone-game-iv/
// Author: github.com/lzl124631x
// Time: O(N * sqrt(N))
// Space: O(N)
int dp[100001] = {[0] = 0, [1 ... 100000] = -1}; // -1 unvisited, 0 loss, 1 win
class Solution {
public:
    bool winnerSquareGame(int n) {
        if (dp[n] != -1) return dp[n];
        for (int i = 1; i * i <= n; ++i) {
            if (!winnerSquareGame(n - i * i)) return dp[n] = 1;
        }
        return dp[n] = 0;
    }
};