368. Sum Game

Count the digit sum and the number of '?' in each half. If the total number of '?' is odd, Alice moves last and can always break a tie. Otherwise the game is a mod-9 balancing contest: Bob wins exactly when the extra question marks on one side can be paired to cancel the known-sum difference (9 per pair).

Building intuition

We never need to simulate the game. Only four numbers matter — for the left half and the right half, the sum of the known digits and the count of '?':

• s_left, q_left — sum and '?' count in num[0 .. n/2)
• s_right, q_right — sum and '?' count in num[n/2 .. n)

Bob wants the two halves to end with equal sums; Alice wants them unequal.

Case 1 — an odd number of '?'

If q_left + q_right is odd, then Alice (who moves first) also makes the last move. Whatever Bob does, Alice fills the final '?' and can choose a digit that leaves the sums unequal. Alice always wins → return true.

Case 2 — an even number of '?'

Now the '?' come in pairs across the whole string, and it turns out both players will effectively pair them up. Think about each pair of blanks:

• If a pair sits on the same half, one player pushes it up and the other pushes it down; the best they can jointly force is a swing of 9 on that half (one plays 9, the other plays 0).
• The blanks therefore behave as q_left free units on the left and q_right on the right, and the two players split them so that the net contribution of the blanks is 4.5 per blank to each side — i.e. 9/2 per blank.

Bob can equalize the halves exactly when the known-sum gap is filled by the blank difference:

2 * (s_left - s_right) == 9 * (q_right - q_left)

Equivalently, Alice wins iff 9 * (q_left - q_right) != 2 * (s_right - s_left).

Steps

1. Walk the string once. For each character, add its value to s_left/s_right, or increment q_left/q_right if it is '?', depending on which half the index falls in.
2. If q_left + q_right is odd, return true.
3. Otherwise return 9 * (q_left - q_right) != 2 * (s_right - s_left).

Walk-through

num = "?3295???", length 8, so half = 4.

Totals: s_left = 14, q_left = 1, s_right = 5, q_right = 3.

q_left + q_right = 4 is even, so use the formula:

• 9 * (q_left - q_right) = 9 * (1 - 3) = -18
• 2 * (s_right - s_left) = 2 * (5 - 14) = -18

They are equal, so Bob can always balance the halves → return false. ✓

Complexity

• Time: O(n) — one pass over the string.
• Space: O(1) — four running counters.

class Solution {
    public boolean sumGame(String num) {
        int n = num.length();
        int half = n / 2;
        int sLeft = 0, qLeft = 0, sRight = 0, qRight = 0;
        for (int i = 0; i < n; i++) {
            char c = num.charAt(i);
            if (i < half) {
                if (c == '?') qLeft++;
                else sLeft += c - '0';
            } else {
                if (c == '?') qRight++;
                else sRight += c - '0';
            }
        }
        if ((qLeft + qRight) % 2 == 1) return true;
        return 9 * (qLeft - qRight) != 2 * (sRight - sLeft);
    }
}