Skip to content

1510. Stone Game IV 👍

  • Time: $O(n^{1.5})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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];
  }
}