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)
1#include <stdbool.h>
2#include <math.h>
3
4bool winnerSquareGame(int n) {
5 bool dp[n+1];
6 for (int i = 0; i <= n; ++i) {
7 dp[i] = false;
8 }
9 for (int i = 1; i <= n; ++i) {
10 for (int k = 1; k*k <= i; ++k) {
11 if (!dp[i-k*k]) {
12 dp[i] = true;
13 break;
14 }
15 }
16 }
17 return dp[n];
18}The array dp is initialized with false values. We iterate through each number up to n, checking all possible square numbers we can subtract. If there exists a square number such that the remaining stones leave Bob in a losing position, Alice is in a winning position.
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)
1#include <vector>
2#include <cmath>
bool isWinning(int n, std::vector<int>& memo) {
if (n == 0) return false;
if (memo[n] != -1) return memo[n];
for (int k = 1; k * k <= n; ++k) {
if (!isWinning(n - k * k, memo)) {
return memo[n] = true;
}
}
return memo[n] = false;
}
bool winnerSquareGame(int n) {
std::vector<int> memo(n+1, -1);
return isWinning(n, memo);
}This C++ solution uses a vector to memoize results. For each position, we recursively evaluate if there are moves leading to a losing state for the opponent. If a losing position is found, it is marked as winning in the memo table.