Intuition
Only each stone's value mod 3 matters. Count how many stones fall in each remainder class 0/1/2. Remainder-0 stones are 'pass' moves that flip who acts; remainder-1 and remainder-2 stones drive the running sum. A short case analysis on those three counts decides the winner.
Explanation
Only the remainder matters
A stone contributes to 'sum divisible by 3' only through its value mod 3. So reduce the whole array to three counts:
c0= stones with value ≡ 0 (mod 3),c1= stones with value ≡ 1 (mod 3),c2= stones with value ≡ 2 (mod 3).
How the game plays out
The running sum's remainder is all that a player watches. A remainder-0 stone changes nothing about the sum's class — it just passes the turn, so c0 acts as a parity switch of who is on the move. The interesting play is with the 1s and 2s: to avoid ever making the sum divisible by 3, a player is forced into a pattern like 1,1,2,2,2,... or 2,2,1,1,1,..., and eventually someone runs out of safe stones.
The decision
if c1 == 0 and c2 == 0: # nothing but multiples of 3
return False # first mover is doomed immediately
if c0 % 2 == 0:
return c1 >= 1 and c2 >= 1 # need both types present to trap opponent
return abs(c1 - c2) > 2 # odd number of 'pass' stones flips it
- No 1s and no 2s: the very first removal makes the sum a multiple of 3, so Alice loses →
false. - Even
c0: the pass-stones cancel out; Alice can force a win exactly when both remainder classes exist (she opens correctly and starves Bob). - Odd
c0: the extra pass flips the parity, and Alice wins only if one class outnumbers the other by more than 2.
Worked example
stones = [2, 1] → remainders [2, 1], so c0 = 0, c1 = 1, c2 = 1.
c1 and c2 aren't both zero; c0 is even, and c1 >= 1 and c2 >= 1 holds → return true. (Alice removes the 2, Bob is squeezed and is forced to hit a multiple of 3.)
Complexity
- Time: O(n) — one pass to bucket the stones, then O(1) decision.
- Space: O(1) — just the three counters.
Implementation
class Solution {
public boolean stoneGameIX(int[] stones) {
// Only each stone's value mod 3 matters; bucket into three counts.
int[] cnt = new int[3];
for (int s : stones) {
cnt[((s % 3) + 3) % 3]++;
}
if (cnt[1] == 0 && cnt[2] == 0) {
return false;
}
if (cnt[0] % 2 == 0) {
return cnt[1] >= 1 && cnt[2] >= 1;
}
return Math.abs(cnt[1] - cnt[2]) > 2;
}
}