Sum Game

Sum Game

What is this problem about?

"Sum Game" is a strategic math game played with a string of even length containing digits and question marks ('?'). The string is divided into two halves. Two players, Alice and Bob, take turns replacing a '?' with any digit from '0' to '9'. Alice goes first. Alice wins if the sum of the digits in the first half is not equal to the sum of the digits in the second half after all '?' are replaced. Bob wins if the sums are equal.

Why is this asked in interviews?

This problem, often seen in interviews for companies like DE Shaw and ByteDance, tests a candidate's ability to analyze game dynamics and simplify them into a greedy or mathematical strategy. Instead of simulating the game (which has a huge state space), the candidate must figure out the "equilibrium" point. It evaluates logical reasoning and the ability to derive a winning condition based on the number of moves available to each player.

Algorithmic pattern used

The core pattern is Greedy logic combined with Mathematical Balancing. Since Bob wants to equalize the sums, he will always try to counter Alice's moves. Each pair of '?' can be used by Bob to offset a difference of 9 (if Alice picks 9, Bob picks 0, or vice versa). The problem boils down to comparing the current difference in sums with the difference in the number of '?' between the two halves. Specifically, Bob wins only if the difference in sums is exactly half of the difference in '?' multiplied by 9, but in the opposite direction.

Example explanation

Suppose the string is "??00". Left half has two '?', right half has zero.

• Alice wants the sum to be unequal. Bob wants them equal.
• Initial sums: Left = 0, Right = 0.
• Question mark counts: Left = 2, Right = 0.
• If Alice puts 9 in the first '?', the string becomes "9?00". Now Bob must put a digit in the second '?' to make the sum 0. But he can't, because even a '0' makes the sum 9.
• In this specific mathematical relationship, Bob wins if (Count?_Left - Count?_Right) * 4.5 == Sum_Right - Sum_Left.

Common mistakes candidates make

1. Simulating the game: Trying to use Minimax or complex recursion. The number of '?' can be large, making simulation impossible.
2. Miscalculating the value of a '?': Forgetting that each pair of moves (one by Alice, one by Bob) can cancel out 9 points, meaning one '?' is worth 4.5 points on average for Bob's balancing act.
3. Ignoring Alice's first-mover advantage: Alice can force the sum to be very high or very low; Bob can only win if the math perfectly allows him to neutralize her.

Interview preparation tip

When you see a game where players choose digits to affect a sum, look for the "pairing" strategy. If one player can always "undo" or "complement" the other player's move, the game usually has a simple mathematical solution. Practice translating wordy game rules into clear algebraic inequalities.