You are playing the following Nim Game with your friend:
Initially, there is a heap of stones on the table.
You and your friend will alternate taking turns, and you go first.
On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
The one who removes the last stone is the winner.
Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.
Example 1:
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.
Example 2:
Input: n = 1
Output: true
Example 3:
Input: n = 2
Output: true
Constraints:
- 1 <= n <= 231 - 1
My Solution
At first glance, we may think about solving this problem with dynamic programming, but looking at the constraints, it’s not feasible. However, we can think about this problem another way. We move first and if there are three or fewer stones, we will win. If there are four stones however, no matter how many stones we take, we will always lose. If there are five stones and we know that the person who has to move with four stones remaining loses, we can just remove one stone and put our opponent in that position. Same applies if there are six or seven stones. If there are eight stones however, no matter how many stones we take on our first turn, our opponent will be in the winning position since the person whose turn it is with five, six or seven stones remaining will win. We start to see the pattern emerge. If we have the first turn and the number of stones remaining is divisible by four, we lose. In all other cases, we win.
Time complexity is O(1) because we just perform one modulo operation. Space complexity is also O(1) since we only require constant extra space.
class Solution {
public boolean canWinNim(int n) {
return (n % 4 != 0);
}
}