Sum Game - Video Solutions

Problem Overview: You are given a numeric string of even length containing digits and '?' characters. The string is split into two equal halves. Players alternately replace '?' with digits 0–9, and Alice wins if the final digit sums of both halves are different. The task is to determine whether Alice can force a win assuming optimal play.

Approach 1: Count '?' and Digits in Each Half (O(n) time, O(1) space)

Traverse the string once and track three values for each half: the digit sum and the number of '?' characters. The difference between the left and right sums determines which side currently has an advantage. Each '?' can change a half's sum by at most 9, so the total potential adjustment depends on how many unknown digits exist on each side. By comparing the current sum difference with the maximum adjustments possible from remaining '?' characters, you can determine if the second player can perfectly balance the sums.

The key observation: if the total number of '?' is odd, Alice automatically wins because she makes the final move and can break equality. If the count is even, check whether the difference in sums can be neutralized by distributing the remaining digits optimally. This turns the problem into simple arithmetic using counts instead of simulating moves.

Approach 2: Game Theory Optimized Detection (O(n) time, O(1) space)

This approach models the game as a deterministic game theory problem. Compute sumLeft, sumRight, and counts of qLeft and qRight. Players try to either maximize or minimize the difference between the halves. Each pair of moves effectively changes the difference by multiples of 9 because a player can place 9 while the opponent may place 0.

If the total number of '?' is odd, Alice has the last move and can always create inequality, guaranteeing a win. If the total is even, evaluate the expression sumLeft - sumRight and compare it with (qRight - qLeft) / 2 * 9. When these values match, Bob can perfectly counter every move and force equal sums. Any other configuration means Alice can push the difference away from zero.

This reasoning avoids simulation and reduces the problem to constant-time arithmetic after a single pass through the string. The logic relies on parity, bounded digit contributions, and optimal adversarial moves—common patterns in greedy and mathematical game problems.

Recommended for interviews: The counting approach is typically expected. It demonstrates that you can convert a turn-based problem into math using digit sums and '?' counts. Explaining the game-theory reasoning behind the balancing formula shows deeper insight and usually impresses interviewers.