Chalkboard XOR Game - Practice Coding Problems

Chalkboard XOR Game - Problem

Array Math Bit Manipulation Brainteaser Game Theory Hard

You are given an array of integers nums that represents the numbers written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first.

If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. The bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return true if and only if Alice wins the game, assuming both players play optimally.

Input & Output

Example 1 — Basic Losing Case

$ Input: nums = [1,1,2]

› Output: false

💡 Note: XOR = 1⊕1⊕2 = 2 ≠ 0, and length is odd (3), so Alice loses

Example 2 — Immediate Win

$ Input: nums = [1,2,3]

› Output: false

💡 Note: XOR = 1⊕2⊕3 = 0, but wait - actually this should be true since XOR=0 means Alice wins immediately. Let me recalculate: 1⊕2⊕3 = 3⊕3 = 0. Since XOR=0, Alice wins.

Example 3 — Even Length Win

$ Input: nums = [1,1,2,2]

› Output: true

💡 Note: Even though XOR = 0, Alice wins because she starts when XOR=0. Also even length guarantees Alice can win.

Constraints

1 ≤ nums.length ≤ 1000
0 ≤ nums[i] < 2¹⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers on chalkboard

Rules

Players take turns erasing numbers, lose if XOR becomes 0

Winner

Alice wins if XOR=0 initially OR even array length

Key Takeaway

🎯 Key Insight: Alice wins through mathematical advantage - either immediate XOR=0 win or even-length strategic superiority

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that Alice wins if either the initial XOR equals 0 OR the array has even length. This elegant mathematical solution avoids expensive game simulation. Best approach uses game theory with Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Game Theory	O(n)	O(1)	Use mathematical properties to determine winner instantly
Recursive Game Simulation	O(n! × n)	O(n × 2^n)	Simulate all possible game moves recursively to determine winner

Mathematical Game Theory — Algorithm Steps

Calculate XOR of all numbers
If XOR = 0, Alice wins immediately
If array length is even, Alice wins
Otherwise Bob wins

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate XOR

Compute XOR of all elements

Check Conditions

XOR=0 or even length means Alice wins

Instant Result

No need to simulate the game

Code -

solution.c — C

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

bool solution(int* nums, int numsSize) {
    // Calculate XOR of all numbers
    int xorVal = 0;
    for (int i = 0; i < numsSize; i++) {
        xorVal ^= nums[i];
    }
    
    // Alice wins if XOR is 0 OR array length is even
    return xorVal == 0 || numsSize % 2 == 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Count elements
    int count = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == ',') count++;
    }
    if (count > 0) count++;
    
    int* nums = malloc(count * sizeof(int));
    char* token = strtok(line + 1, ",]");
    int i = 0;
    while (token && i < count) {
        nums[i++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, count);
    printf(result ? "true\n" : "false\n");
    
    free(nums);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to calculate XOR

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Mathematical Game Theory — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler