Sum game

Math String Greedy Game Theory

49.6% acceptance

Feb 25, 2026

541

Alice and Bob take turns playing a game, with Alice starting first. You are given a string num of even length consisting of digits and '?' characters. On each turn, a player will do the following if there is still at least one '?' in num: Choose an index i where num[i] == '?'. Replace num[i] with any digit between '0' and '9'. The game ends when there are no more '?' characters in num. For Bob to win, the sum of the digits in the first half of num must be equal to the sum of the digits in the second half. For Alice to win, the sums must not be equal. Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sum_game(num: String) -> bool {
    let n = num.len();
    let half = n / 2;
    let bytes = num.as_bytes();
    let mut sum1 = 0i64;
    let mut q1 = 0i64;
    let mut sum2 = 0i64;
    let mut q2 = 0i64;

    for i in 0..half {
      if bytes[i] == b'?' {
        q1 += 1;
      } else {
        sum1 += (bytes[i] - b'0') as i64;
      }
    }
    for i in half..n {
      if bytes[i] == b'?' {
        q2 += 1;
      } else {
        sum2 += (bytes[i] - b'0') as i64;
      }
    }

    // If total question marks is odd, Alice always wins
    if (q1 + q2) % 2 == 1 {
      return true;
    }

    // Bob wins iff sum1 + 9*q1/2 == sum2 + 9*q2/2
    // (each pair of moves on same side nets 9: Alice puts 9, Bob puts 0 or vice versa)
    // Multiply by 2 to avoid fractions:
    // 2*sum1 + 9*q1 == 2*sum2 + 9*q2
    2 * sum1 + 9 * q1 != 2 * sum2 + 9 * q2
  }
}