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).
1class Solution:
2 def canWinNim(self, n: int) -> bool:
3 return n % 4 != 0In Python, the solution uses the modulus operator to decide the winnability by checking if n is not divisible by 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.
1This C solution uses a cyclic buffer to store states and computes dynamically from known base conditions. The buffer size is 4 because we only need the last 3 results to compute the current state.