Nim Game — Solution in Python, Java & C++
Nim Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.
Nim Game is an easy coding problem on math, game theory and brainteaser, asked in Amazon, Adobe and Bloomberg interviews.
- Difficulty: Easy
- Topics: Math, Game Theory, Brainteaser
- Asked at: Amazon, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You and a friend take turns removing 1, 2 or 3 stones from a heap of n stones. You move first, and whoever removes the last stone wins.
Assuming both of you play optimally, return true if you can win.
Example 1
Input: n = 4
Output: false
Explanation: Whatever you take, your friend can clear the rest.
Example 2
Input: n = 1
Output: true
Example 3
Input: n = 2
Output: true
Constraints
1 <= n <= 1000000000
Hints for Nim Game
Hint 1
Work out small cases by hand: 1, 2 and 3 are wins; 4 is a loss.
Hint 2
From 5, 6 or 7 you can always hand your opponent exactly 4.
Hint 3
The losing positions are precisely the multiples of 4.
How to solve Nim Game
Multiples of four are losing positions: from any other count you can leave a multiple of four, and from a multiple of four every move leaves a non-multiple.
Approach
- Return
n % 4 != 0.
Why it works
By induction from 0 (a loss for the player to move): from 4k + r with r ∈ {1, 2, 3} take r stones; from 4k any move of 1–3 leaves 4k - 1..4k - 3, all winning for the opponent.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- The DP over
npositions reproduces this pattern and is a fine way to discover it.
Reference solution
Python
def canWinNim(n: int) -> bool:
return n % 4 != 0Java
public static boolean canWinNim(int n) {
return n % 4 != 0;
}C++
bool canWinNim(int n) {
return n % 4 != 0;
}JavaScript
var canWinNim = function(n) {
return n % 4 !== 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.