Stone Game IX

Stone Game IX

What is this problem about?

In Stone Game IX, Alice and Bob play a game with an array of stones. Alice goes first. On each turn, a player removes a stone and adds its value to a running sum. The player loses if the current sum becomes divisible by 3 after their turn, or if they are forced to take a stone when no stones are left (in which case Bob wins if any stones were originally there, under specific rules). The stones' actual values don't matter as much as their values modulo 3.

Why is this asked in interviews?

This problem is a favorite at Samsung and Google because it tests your ability to simplify complex game rules using mathematical observations. It requires you to categorize items (counting stones with remainder 0, 1, or 2) and analyze the game's flow based on these counts. It's a great test of Math, Counting, and Game Theory interview pattern knowledge.

Algorithmic pattern used

The primary pattern is Counting and Game Theory. You count how many stones have remainders 0, 1, and 2 when divided by 3. Stones with remainder 0 are "neutral"—they don't change the sum's divisibility by 3, but they can be used to pass the turn back and forth. The game's outcome mostly depends on the relative counts of remainder-1 and remainder-2 stones and whether the number of remainder-0 stones is even or odd.

Example explanation (use your own example)

Suppose you have:

• Two stones with remainder 1.
• Two stones with remainder 2.
• Zero stones with remainder 0. Alice starts. If she picks a remainder-1 stone, the sum is 1. Now Bob can pick a remainder-1 stone (sum 2) or a remainder-2 stone (sum 3, he loses). Bob picks remainder-1. Sum is 2. Now Alice must pick a remainder-2 stone (sum 4) or she loses. If she picks remainder-2, sum is 4. Finally, Bob must pick remainder-2, sum is 6, Bob loses. Alice wins!

Common mistakes candidates make

• Simulating the game: Trying to use recursion with memoization when a constant-time mathematical check is possible.
• Ignoring remainder-0 stones: Not realizing that stones with remainder 0 can change who is forced to make a "losing" move.
• Incorrect win conditions: Misinterpreting what happens when all stones are removed.
• Complexity: Overcomplicating the logic with too many if-else branches instead of finding the underlying parity rules.

Interview preparation tip

When a problem involves divisibility, always think about the remainder (modulo). Categorizing the input into remainders often reveals a pattern that makes the full simulation unnecessary.