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).
1#include <stdbool.h>
2bool canWinNim(int n) {
3 return n % 4 != 0;
4}The code checks the remainder of n divided by 4. If the remainder is not zero, you can win; otherwise, you lose.
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.
1publicIn Java, this solution uses an array to cyclically store winning states for the game. It builds solution progressively based on previous results.