Nim Game

Easy
422.

Nim Game

Nim Game is an easy coding problem on math, game theory and brainteaser, asked in Amazon, Adobe and Bloomberg interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Work out small cases by hand: 1, 2 and 3 are wins; 4 is a loss.

  2. Hint 2

    From 5, 6 or 7 you can always hand your opponent exactly 4.

  3. 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

  1. 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 n positions reproduces this pattern and is a fine way to discover it.

Reference solution

Python

def canWinNim(n: int) -> bool:
    return n % 4 != 0

Java

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.

All 337 math problems · the whole catalogue