Game of Nim - Practice Coding Problems

Game of Nim - Problem

Array Math Dynamic Programming Bit Manipulation Brainteaser Game Theory Medium

Alice and Bob take turns playing a game with Alice starting first. In this game, there are n piles of stones. On each player's turn, the player should remove any positive number of stones from a non-empty pile of his or her choice.

The first player who cannot make a move loses, and the other player wins. Given an integer array piles, where piles[i] is the number of stones in the i^th pile, return true if Alice wins, or false if Bob wins.

Both Alice and Bob play optimally.

Input & Output

Example 1 — Basic Nim Game

$ Input: piles = [1,3,5]

› Output: true

💡 Note: XOR of all piles: 1 ⊕ 3 ⊕ 5 = 7 ≠ 0, so Alice (first player) wins

Example 2 — Balanced Position

$ Input: piles = [1,1]

› Output: false

💡 Note: XOR of all piles: 1 ⊕ 1 = 0, so Bob (second player) wins

Example 3 — Single Pile

$ Input: piles = [5]

› Output: true

💡 Note: XOR = 5 ≠ 0, Alice can take all stones and wins

Constraints

1 ≤ piles.length ≤ 7
1 ≤ piles[i] ≤ 7

Visualization

Tap to expand

Understanding the Visualization

Input

Array of pile sizes [1,3,5]

Process

XOR all values: 1⊕3⊕5 = 7

Output

7 ≠ 0 → Alice wins → true

Key Takeaway

🎯 Key Insight: The XOR of all pile sizes instantly reveals the winner without simulating the game

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is the Nim theorem: Alice wins if and only if the XOR of all pile sizes is non-zero. Best approach is bit manipulation using XOR operation. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Nim Theorem (XOR Solution)	O(n)	O(1)	Use Nim theorem: Alice wins if XOR of all pile sizes is non-zero
Recursive Game Simulation	O(2^n)	O(n)	Simulate all possible game moves recursively to determine the winner

Nim Theorem (XOR Solution) — Algorithm Steps

Calculate XOR of all pile sizes
If XOR equals 0, second player (Bob) wins
If XOR is non-zero, first player (Alice) wins

Visualization

Tap to expand

Step-by-Step Walkthrough

XOR Calculation

Compute XOR of all pile sizes

Check Result

If XOR ≠ 0, Alice wins; if XOR = 0, Bob wins

Winner

Return true for Alice, false for Bob

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* piles, int n) {
    // Nim theorem: first player wins iff XOR of all piles is non-zero
    int nimSum = 0;
    for (int i = 0; i < n; i++) {
        nimSum ^= piles[i];
    }
    
    return nimSum != 0;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int piles[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num > 0 || strcmp(token, "0") == 0) {
            piles[n++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    bool result = solution(piles, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to compute XOR of all elements

✓ Linear Growth

Space Complexity

O(1)

Only uses one variable to store running XOR result

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Nim Theorem (XOR Solution) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler