Stone Game IX - Practice Coding Problems

Stone Game IX - Problem

Array Math Greedy Counting Game Theory Medium

Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.

Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).

Assuming both players play optimally, return true if Alice wins and false if Bob wins.

Input & Output

Example 1 — Alice Wins

$ Input: stones = [2,1]

› Output: true

💡 Note: Alice picks 2 (sum=2), Bob must pick 1 (sum=3), Bob loses since 3 is divisible by 3

Example 2 — Bob Wins

$ Input: stones = [2]

› Output: false

💡 Note: Alice must pick 2 (sum=2), no stones left for Bob, so Bob wins automatically

Example 3 — Only Multiples of 3

$ Input: stones = [3,6,9]

› Output: false

💡 Note: Any first move by Alice creates sum divisible by 3, so Alice loses immediately

Constraints

1 ≤ stones.length ≤ 10⁵
1 ≤ stones[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone values: [2,1]

Game Play

Players alternate, lose if sum ≡ 0 (mod 3)

Output

true if Alice wins, false if Bob wins

Key Takeaway

🎯 Key Insight: Alice wins if she can force Bob into making a sum divisible by 3

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The key insight is that Alice loses if she's forced to make the running sum divisible by 3. Group stones by remainder mod 3 and use game theory to check if Alice can maintain a winning pattern. Best approach uses counting with game theory in O(n) time, O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Game Theory with Counting	O(n)	O(1)	Count stones by remainder mod 3 and analyze winning conditions
Brute Force Recursion	O(2^n)	O(n)	Recursively try all possible moves for both players

Game Theory with Counting — Algorithm Steps

Count stones with remainder 0, 1, 2 when divided by 3
Analyze if Alice can start a winning sequence
Check if Alice can maintain control without hitting sum divisible by 3

Visualization

Tap to expand

Step-by-Step Walkthrough

Group Stones

Count stones by remainder when divided by 3

Try Starting Moves

Alice can start with remainder 1 or 2 stones

Check Win Condition

Verify Alice can maintain control

Code -

solution.c — C

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

bool canWinFromState(int count1, int count2, int count0, int nextRemainder) {
    if (nextRemainder == 1) {
        if (count1 == 0) {
            return count0 % 2 == 1;
        }
        return count2 >= count1 - 1 && (count1 + count2 + count0) % 2 == 1;
    } else {
        if (count2 == 0) {
            return count0 % 2 == 1;
        }
        return count1 >= count2 - 1 && (count1 + count2 + count0) % 2 == 1;
    }
}

bool solution(int* stones, int n) {
    // Count stones by remainder when divided by 3
    int count[3] = {0, 0, 0};
    for (int i = 0; i < n; i++) {
        count[stones[i] % 3]++;
    }
    
    // If no stones with remainder 1 or 2, Alice loses
    if (count[1] == 0 && count[2] == 0) {
        return false;
    }
    
    // Try starting with remainder 1
    if (count[1] > 0) {
        int remaining1 = count[1] - 1;
        int remaining2 = count[2];
        int remaining0 = count[0];
        
        if (canWinFromState(remaining1, remaining2, remaining0, 2)) {
            return true;
        }
    }
    
    // Try starting with remainder 2
    if (count[2] > 0) {
        int remaining1 = count[1];
        int remaining2 = count[2] - 1;
        int remaining0 = count[0];
        
        if (canWinFromState(remaining1, remaining2, remaining0, 1)) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int stones[1000];
    int n = 0;
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && n < 1000) {
            stones[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    bool result = solution(stones, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count stones by remainder

✓ Linear Growth

Space Complexity

O(1)

Only storing three counters

✓ Linear Space

28.5K Views

Medium Frequency

~35 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

Game Theory with Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler