Stone Game IX
Alice and Bob take turns removing stones from a collection, with Alice going first.
Each stone has a value stones[i]. On a player's turn, they remove one stone. The game ends when the sum of all removed stones is divisible by 3. The player who makes the sum divisible by 3 loses.
If neither player can make a move (no stones left) and the sum is not divisible by 3, the game is a draw. Return "Alice" if Alice wins, "Bob" if Bob wins, or "Draw" otherwise.
Examples
Input: [2,1]
Output: "Alice"
Input: [1,1,1]
Output: "Bob"
Hints
Only the remainder modulo 3 of each stone matters. Categorize stones into three groups: remainder 0, 1, and 2.
If there are no remainder-1 or remainder-2 stones, Alice loses immediately since the only moves are remainder-0 which keep the sum unchanged and make Alice take the 3rd 0-stone.
Count occurrences of each remainder. Simulate both possible first moves for Alice (a remainder-1 or remainder-2 stone) and check if she can force a win.
Related Problems
Stone Game IX
Alice and Bob take turns removing stones from a collection, with Alice going first.