Stone game ix

Array Math Greedy Counting Game Theory

30.0% acceptance

Feb 25, 2026

261

280

Alice and Bob play a game with stones. Stones have values. Players take turns (Alice first). Player loses if sum of removed stones is divisible by 3. Bob wins if all stones removed without losing. Return true if Alice wins with optimal play.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn stone_game_ix(stones: Vec<i32>) -> bool {
    let mut cnt = [0i32; 3];
    for s in stones { cnt[(s % 3) as usize] += 1; }
    
    // Key insight based on analysis of the game:
    // c0 = count of multiples of 3
    // c1 = count where stone % 3 == 1
    // c2 = count where stone % 3 == 2
    if cnt[0] % 2 == 0 {
      // Alice wins if both c1 > 0 and c2 > 0
      cnt[1] > 0 && cnt[2] > 0
    } else {
      // Alice wins if |c1 - c2| > 2
      (cnt[1] - cnt[2]).abs() > 2
    }
  }
}