Scale Engineer

Nim Game

Easy
#0279Time: O(3^n) - For each position, we make 3 recursive callsSpace: O(n) - Maximum depth of recursion tree
Patterns
MathGame Theory

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

We can solve this problem using recursion by trying all possible moves and checking if any of them leads to a winning position.

Algorithm

  1. Check base cases:
    • If n ≤ 0, return false
    • If n ≤ 3, return true
  2. Recursively check if we can win by trying all possible moves
  3. Return true if any move leads to a winning position

Walkthrough

In this approach, we use recursion to simulate all possible moves and determine if we can win. For each turn:

  1. Base cases:

    • If n = 0, return false (no stones left)
    • If n = 1, 2, or 3, return true (can take all stones)

  2. For each possible move (1, 2, or 3 stones), we:

    • Make the move by subtracting stones
    • Recursively check if opponent can win with remaining stones
    • If opponent can't win, we win

Here's the implementation:

public boolean canWinNim(int n) {    if (n <= 0) return false;    if (n <= 3) return true;        // Try removing 1, 2, or 3 stones    return !(canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3));}

Complexity

Time

O(3^n) - For each position, we make 3 recursive calls

Space

O(n) - Maximum depth of recursion tree

Trade-offs

Pros

  • Easy to understand and implement

  • Directly simulates the game process

  • Works for small inputs

Cons

  • Extremely inefficient for large inputs

  • Will cause stack overflow for large n

  • Many redundant calculations

Solutions

class Solution {public  boolean canWinNim(int n) { return n % 4 != 0; }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem