Stone Game IX

Medium
861.

Stone Game IX

Stone Game IX is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Directi interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stones
 * @return {boolean}
 */
var stoneGameIX = function(stones) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stone Game IX — Solution in Python, Java & C++

Stone Game IX solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and math.

Stone Game IX is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Directi interviews.

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

Hints for Stone Game IX

  1. Hint 1

    Only each stone's value modulo 3 matters — group them into counts c0, c1 and c2.

  2. Hint 2

    A stone with residue 0 never changes the running total's residue; it just passes the turn.

  3. Hint 3

    So the parity of c0 decides who effectively moves first in the alternating 1/2 sequence.

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

Java

public static boolean stoneGameIX(int[] stones) {
    int[] c = new int[3];
    for (int x : stones) c[x % 3]++;
    if (c[0] % 2 == 0) return c[1] >= 1 && c[2] >= 1;
    return Math.abs(c[1] - c[2]) > 2;
}

C++

bool stoneGameIX(vector<int>& stones) {
    int c[3] = { 0, 0, 0 };
    for (int x : stones) c[x % 3]++;
    if (c[0] % 2 == 0) return c[1] >= 1 && 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms