292. Nim Game

EasyBrainteaserMathGame Theory

Problem Description

In the Nim Game, you are up against a friend with a pile of stones on the table. Players take turns, with you in the lead, each turn allowing the removal of 1 to 3 stones from the pile. The main objective is to be the person who takes the last stone, as this means victory. The challenge posed to you is a strategy one: given the total number n of stones, can you determine whether success is in your reach assuming both players adopt an optimal playing strategy? Your task is to compute a function that inputs the number of stones n and outputs true if winning is possible, or false otherwise.

Intuition

To intuitively reason why the provided solution works, let's break down the game for different initial amounts of stones:

If n is between 1 and 3, you can win by taking all the stones.
If n is 4, no matter how many you take, your friend can always take the remainder and win.
If n is between 5 and 7, you can always take enough stones to leave your friend with 4 stones, which, as stated above, leads to a guaranteed win for you.
If n is 8, any move you make will leave a number between 5 and 7 for your friend, which allows them to leave you with 4 stones, leading to their win.

Noticing this pattern, we can see that if n is a multiple of 4, you will inevitably lose, because no matter how many stones you take, your friend can always take an amount that will leave a multiple of 4 for your next turn, putting you at a disadvantage until the end when you are left with the fatal 4 stones.

Therefore, the key observation is that the number 4 is a "losing" number. If the starting number n is not a multiple of 4, you can win by taking enough stones to bring the total down to a multiple of 4. After that, you can mirror your friend's moves to ensure you always leave them with a multiple of 4 stones, thereby securing your victory.

This boils down the solution to a simple modulo operation. If n % 4 != 0, you can win Nim Game by making the first move that leaves your friend with a multiple of 4 stones; otherwise, you cannot guarantee a win if both of you play optimally.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Solution Approach

The implementation of the solution for the Nim Game problem is succinct and relies on an arithmetic operation known as the modulo operation. The entire solution is encapsulated in a single line of code within the method canWinNim, which takes an integer n as an argument and returns a boolean value.

Here's how the solution method is implemented:

1class Solution:
2    def canWinNim(self, n: int) -> bool:
3        return n % 4 != 0

The algorithm behind this approach is straightforward: since we've established that 4 is the "losing" number for the game (i.e., if you start your turn with 4 stones, you cannot win if your opponent plays optimally), we want to check if the current number of stones n is a losing number. We do this by calculating n % 4 — the remainder when n is divided by 4.

If the remainder is not equal to zero (n % 4 != 0), this means that n is not a multiple of 4, and therefore, you can make the first move to leave a multiple of 4 stones to your opponent. Consequently, you have a winning strategy.

No additional data structures or complex patterns are needed; the modulo operation is the sole driver of this logic, evidencing the elegance and efficiency of the solution - a true demonstration of understanding the problem's inherent mathematical pattern, which simplifies the algorithm to a single, decisive operation that runs in constant time with constant space complexity.

In summary, whenever confronted with this particular instance of the Nim Game:

If n % 4 == 0, this signals your defeat - hence, return false.
If n % 4 != 0, victory is in your grasp if you use the correct strategy, making the appropriate removals on each turn - hence, return true.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Example Walkthrough

Let's assume we have a pile of 6 stones (n = 6). Using the solution approach described, let's walk through the game:

Check the total number of stones using the modulo operation: n % 4.
If n % 4 != 0, that means you have a winning strategy.
In our case, 6 % 4 equals 2, which is not equal to zero. Therefore, you can win.
To implement the winning strategy, you need to take stones in such a way that you leave a multiple of 4 stones for your opponent. Since 6 is not a multiple of 4, you should take 2 stones first.
Now there are 4 stones left, which is a multiple of 4. This is the "losing" number for whoever's turn it is to play.
Your opponent can take 1, 2, or 3 stones, but no matter what they take, you will be able to take the remainder and win the game.
Your opponent takes 1 stone (best move for them), leaving 3 stones.
You take all 3 remaining stones, winning the game.

According to the solution approach, as long as you start with a number that is not a multiple of 4, you can always force a win. If the number had been 8 (which is a multiple of 4), you would be at a losing position assuming optimal play from your opponent. This walkthrough illustrates the simplicity and effectiveness of the modulo-based solution where the key to winning is avoiding leaving a pile of 4 stones for your turn.

Solution Implementation

1class Solution:
2    def canWinNim(self, n: int) -> bool:
3        # In the game of Nim, you can win if the number of stones 'n'
4        # is not a multiple of 4. If 'n' % 4 == 0, your opponent can
5        # always play optimally and leave you in a position where you'll
6        # eventually lose. Therefore, you can only win if 'n' % 4 != 0.
7        return n % 4 != 0
8

1class Solution {
2    // Method to determine if you can win the Nim game given the number of stones.
3    public boolean canWinNim(int n) {
4        // In the game of Nim, you can always win if the number of stones 
5        // is not a multiple of 4. If it is a multiple of 4, you will
6        // inevitably lose if your opponent plays optimally, because no matter 
7        // how many stones you take (1 to 3), your opponent can always take 
8        // a number that sums up to 4 with your move, eventually leaving you
9        // with the last 4 stones, which you will be forced to take.
10        return n % 4 != 0;
11    }
12}
13

1class Solution {
2public:
3    // Determines if the player can win the Nim game given the number of stones.
4    // The player can win the game unless the number of stones is a multiple of four.
5    bool canWinNim(int numberOfStones) {
6        // If the remainder of 'numberOfStones' divided by 4 is not zero,
7        // the player can win by making a strategic move.
8        return numberOfStones % 4 != 0;
9    }
10};
11

1/**
2 * Determines if you can win the game of Nim given the total number of stones.
3 * The player can win if the number of stones is not a multiple of 4.
4 * 
5 * @param {number} totalStones - The total number of stones in the game.
6 * @returns {boolean} - True if the player can win, false otherwise. 
7 */
8function canWinNim(totalStones: number): boolean {
9    // A player can win if the remaining stones are not a multiple of 4.
10    // If the number of stones is a multiple of 4, no matter how the player plays,
11    // the opponent can always leave a multiple of 4 stones after their turn,
12    // eventually leaving the player with exactly 4 stones on their turn, which
13    // forces them to lose. Therefore, the player can only win if the starting
14    // number of stones is not a multiple of 4.
15    return totalStones % 4 !== 0;
16}
17

Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayMerge sort does not use divide and conquer

I don’t know

Time and Space Complexity

The time complexity of the code is O(1) as the operation performed is a single modulus calculation, which takes constant time regardless of the value of n.

The space complexity of the code is also O(1) because the algorithm only uses a fixed amount of space; no additional space is utilized that is dependent on the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological SortUniform Cost SearchMonotonic StackMemoization

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

292. Nim Game

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings