Sum Game: Game Theory with Greedy Analysis

Alice and Bob take turns filling in ? characters in a string num of even length. Alice goes first. Each ? is replaced with a single digit (0-9). When all ? characters are filled, Bob wins if the sum of the first half of digits equals the sum of the second half. Otherwise, Alice wins. Both players play optimally. Return true if Alice will win the game.

This is LeetCode 1927: Sum Game, a medium problem that looks like it needs game simulation but collapses into a clean mathematical condition once you understand the structure of optimal play.

Why this problem matters

Sum Game is one of the rare LeetCode problems that tests game theory combined with greedy reasoning. Most interview candidates try to simulate every possible move sequence, which explodes combinatorially. The real trick is recognizing that optimal play from both sides produces a deterministic outcome you can compute in O(n) time.

This problem also drills the skill of reducing a game to a closed-form condition. Instead of thinking about sequences of moves, you analyze the final state that optimal play must produce. That shift in perspective, from simulation to invariant, is a pattern that shows up in many competitive programming problems and system design scenarios.

Breaking down the conditions

There are three variables that matter: the digit sum of the first half (sum1), the digit sum of the second half (sum2), the count of ? characters in the first half (q1), and the count in the second half (q2).

Alice wins immediately in two situations:

1. Odd total question marks. If q1 + q2 is odd, Alice gets one more turn than Bob. She can always use that extra move to break the balance. Bob can never recover because he runs out of moves first.

2. The sum difference does not match the pair rule. When q1 + q2 is even, consider that each "pair" of question marks (one filled by Alice, one by Bob) contributes exactly 9 to the running balance. Alice places 9 on one side, and Bob is forced to place 0 on his side (or vice versa). The net swing per pair is always 9.

Bob wins only when the total question mark count is even AND the difference sum1 - sum2 equals exactly 9 * (q2 - q1) / 2. In every other case, Alice wins.

The solution

def sum_game(num):
    n = len(num)
    half = n // 2
    sum1 = sum2 = q1 = q2 = 0

    for i in range(n):
        if num[i] == '?':
            if i < half:
                q1 += 1
            else:
                q2 += 1
        else:
            if i < half:
                sum1 += int(num[i])
            else:
                sum2 += int(num[i])

    if (q1 + q2) % 2 == 1:
        return True

    return (sum1 - sum2) != 9 * (q2 - q1) // 2

The logic follows directly from the conditions we identified. First, count the digit sums and question marks for each half. If the total question marks is odd, Alice wins automatically. Otherwise, check whether the existing sum difference aligns with the expected contribution of paired question marks (9 per pair). If it does not align, Alice wins.

Why the 9-per-pair rule works

Consider a single pair of question marks, one in each half. Alice goes first. If Alice places digit a in one half, Bob can respond with digit b in the other half, or vice versa. Alice wants to maximize the imbalance, and Bob wants to equalize.

If Alice places 9 in the first half, Bob's best response is to place 9 in the second half. That adds 9 to each side, netting 0 change. But if both ? characters are on the same side, Alice places 9 and Bob places 0, netting 9. The key insight is that for paired ? characters across halves, Bob can neutralize Alice. For unpaired ? characters on one side, each pair (Alice + Bob turn) contributes a net of 9.

Working through the algebra: if there are more ? characters in the second half than the first, each excess pair of ? characters lets Alice push 9 units of sum into the second half. For Bob to win, the existing deficit sum1 - sum2 must exactly equal 9 * (q2 - q1) / 2.

Complexity analysis

One pass through the string to count sums and question marks, then a constant-time check. This is optimal since you need to read every character at least once.

Edge cases to watch for

• No question marks at all. If q1 + q2 = 0, compare sum1 and sum2 directly. If they are equal, Bob wins (return false). Otherwise, Alice wins (return true). But since there are no moves to make, "Alice wins" really means the sums were already unequal.
• All question marks. If every character is ?, then sum1 = sum2 = 0 and q1 = q2 = n/2. The total is even. The difference is 0, and 9 * (q2 - q1) / 2 = 0. So Bob wins (return false).
• Question marks on one side only. For example, num = "25??". The odd/even check determines whether Alice gets an extra move. If the count is even, check the 9-per-pair condition.
• Large inputs. The string can be up to 10^5 characters. The O(n) solution handles this without issues.

The building blocks

This problem rests on two reusable patterns.

1. Game theory invariant

Instead of simulating moves, identify an invariant that optimal play preserves. In Sum Game, the invariant is that each pair of moves swings the balance by exactly 9. This reduces the game tree to a single algebraic check. The same approach works in Nim-style problems, Sprague-Grundy analysis, and any game where you can characterize the final state without enumerating moves.

2. Greedy first-mover advantage

Alice moves first, which gives her control when the total number of moves is odd. She will always have one more move than Bob, so she can always break symmetry. Recognizing when a first-mover advantage is decisive is a common pattern in combinatorial game theory. You will see it in problems like Stone Game variants and many two-player optimization games.

From understanding to recall

You have read the solution and the 9-per-pair rule makes sense. One pass, two conditions, done. But can you write it from scratch in an interview without looking at it?

The details matter: counting q1 and q2 separately for each half, checking odd total first, and getting the sign right in the 9 * (q2 - q1) // 2 formula. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sum-and-count loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "game with two halves, question marks, optimal play" and the code flows out without hesitation.

The game theory invariant pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Gas Station - Greedy single-pass problem with a circular structure
• Jump Game - Greedy forward-scanning to determine reachability
• Candy - Greedy with two-pass analysis

CodeBricks breaks the sum game LeetCode problem into its game theory invariant and greedy first-mover advantage building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a game theory question shows up in your interview, you do not think about it. You just write it.