Get started

Stone Game IX — Medium Problem & Solution

Alice and Bob take turns removing one stone, Alice first. A player loses immediately if, after their removal, the total value of all removed stones is…

Problem statement

Alice and Bob take turns removing one stone, Alice first. A player loses immediately if, after their removal, the total value of all removed stones is divisible by 3. If every stone is removed without that happening, Bob wins.

Assuming both play optimally, return whether Alice wins.

Example 1

Input: stones = [2,1]
Output: true
Explanation: Alice removes 2; Bob must remove 1, making the total 3.

Example 2

Input: stones = [2]
Output: false
Explanation: Alice removes the only stone and the game ends with Bob winning.

Example 3

Input: stones = [5,1,2,4,3]
Output: false

Constraints

  • 1 <= stones.length <= 100000
  • 1 <= stones[i] <= 10000

How to solve Stone Game IX

Reduce to residues. Stones with residue 0 are pure turn-passers, so only the parity of c0 matters; the game itself is then a forced alternation between residues 1 and 2 that Alice must sustain.

Approach

  1. Count stones by residue mod 3 into c0, c1, c2.
  2. If c0 is even, Alice wins exactly when both c1 >= 1 and c2 >= 1.
  3. If c0 is odd, Alice wins exactly when |c1 - c2| > 2.

Why it works

Starting with a residue-1 stone forces the sequence 1, 1, 2, 1, 2, … to avoid a multiple of 3, and starting with a 2 mirrors it — so Alice needs at least one of each to get a viable opening. An even c0 leaves the parity of the alternation untouched. An odd c0 hands the effective first move to the opponent, and Alice can only survive by exhausting one residue class far enough ahead of the other, which is exactly the gap of more than 2.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Simulating the game is exponential; only the three counts matter.
  • The c0 parity flips which player is under pressure — swapping the two branches inverts every answer.
  • The threshold in the odd case is strictly greater than 2, not at least 2.

Reference solution

Python

from typing import List

def stoneGameIX(stones: List[int]) -> bool:
    c = [0, 0, 0]
    for x in stones:
        c[x % 3] += 1
    if c[0] % 2 == 0:
        return c[1] >= 1 and c[2] >= 1
    return abs(c[1] - c[2]) > 2

JavaScript

var stoneGameIX = function(stones) {
    var c = [0, 0, 0];
    for (var i = 0; i < stones.length; i++) c[stones[i] % 3]++;
    if (c[0] % 2 === 0) return c[1] >= 1 && c[2] >= 1;
    return Math.abs(c[1] - c[2]) > 2;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue