Sponsored
Sponsored
This approach uses Dynamic Programming to determine if Alice can win given n stones. We can maintain a boolean array dp where dp[i] represents whether Alice can win with i stones. A state is winning if there's any move that leaves the opponent in a losing state.
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
1import java.util.*;
2
3public class Solution {
4 public boolean winnerSquareGame(int n) {
5 boolean[] dp = new boolean[n + 1];
6 for (int i = 1; i <= n; i++) {
7 for (int k = 1; k * k <= i; k++) {
8 if (!dp[i - k * k]) {
9 dp[i] = true;
10 break;
11 }
12 }
13 }
14 return dp[n];
15 }
16}A boolean array is used to keep track of winning positions. For each number of stones, we check if removing any perfect square leaves a losing state for the opponent.
This approach involves a recursive solution with memoization to cache previously computed results. If n is already solved, we return the cached result. Otherwise, we recursively check if any move leaves the opponent in a losing position.
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
1using System;
2
public class Solution {
public bool WinnerSquareGame(int n) {
int?[] memo = new int?[n + 1];
return IsWinning(n, memo);
}
private bool IsWinning(int n, int?[] memo) {
if (n == 0) return false;
if (memo[n] != null) return memo[n] == 1;
for (int k = 1; k * k <= n; ++k) {
if (!IsWinning(n - k * k, memo)) {
memo[n] = 1;
return true;
}
}
memo[n] = 0;
return false;
}
}The C# solution uses a helper function to recursively determine result states, caching outcomes in the memo array. The recursion checks if removing a perfect square results in a losing state for the opponent.