Sponsored
Sponsored
In this approach, the key observation is that if n is a multiple of 4, you will lose the game if both play optimally. Hence, you can immediately return false in this case. The reason is that no matter what you do (removing 1 to 3 stones), you will leave the opponent with a number of stones that are not a multiple of 4, enabling them to adjust their removal so that you fail.
Time Complexity: O(1).
Space Complexity: O(1).
1public class Solution {
2 public boolean canWinNim(int n) {
3 return n % 4 != 0;
4 }
5}The Java code follows the same logic using the modulo operator to check if the number of stones is not a multiple of 4.
A more generalized approach can be a dynamic programming technique to solve the problem for smaller values and build up the solution by using previously solved values. This approach can be used when learning optimal sub-structure is more relevant and the pattern is not known beforehand.
Time Complexity: O(n).
Space Complexity: O(1) due to constant space usage.
However, it is important to note for large n, this specific approach might be constrained by array size limitations in practice.
1public:
bool canWinNim(int n) {
if (n <= 3) return true;
bool dp[4] = {true, true, true, false};
for (int i = 4; i <= n; i++) {
dp[i % 4] = !dp[(i-1) % 4] || !dp[(i-2) % 4] || !dp[(i-3) % 4];
}
return dp[n % 4];
}
};This C++ solution employs dynamic programming with a cyclic buffer of 4 elements to determine if the current position is winnable by looking at any of the previous 3 sub-games.