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:
i where num[i] == '?'.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.
num = "243801", then Bob wins because 2+4+3 = 8+0+1. If the game ended with num = "243803", then Alice wins because 2+4+3 != 8+0+3.Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.
Example 1:
Input: num = "5023" Output: false Explanation: There are no moves to be made. The sum of the first half is equal to the sum of the second half: 5 + 0 = 2 + 3.
Example 2:
Input: num = "25??" Output: true Explanation: Alice can replace one of the '?'s with '9' and it will be impossible for Bob to make the sums equal.
Example 3:
Input: num = "?3295???" Output: false Explanation: It can be proven that Bob will always win. One possible outcome is: - Alice replaces the first '?' with '9'. num = "93295???". - Bob replaces one of the '?' in the right half with '9'. num = "932959??". - Alice replaces one of the '?' in the right half with '2'. num = "9329592?". - Bob replaces the last '?' in the right half with '7'. num = "93295927". Bob wins because 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7.
Constraints:
2 <= num.length <= 105num.length is even.num consists of only digits and '?'.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.
This approach involves counting the number of '?' marks and sum of digits for the first half and the second half separately. The difference in the counts determines the control each player has over the final outcome, and hence the winner.
This C solution evaluates the difference in sum after separating the string into two halves. It considers '?' marks as zeros initially, then adjusts potential maximum impacts of unknown digits while comparing sums from each half.
The time complexity is O(n) since we need to traverse the string once to gather necessary information, and the space complexity is O(1) because we are using a constant amount of extra space.
Using game theory, examine the outcomes based on current sums and '?'. Depending on whether '?' can be resolved advantageously (or leave it neutral), predict if Alice can always prevent Bob's win.
This strategy considers the equality of options (both sides having equal '?'), simplifying the decision into whether the current sum balance can diverge, helping Alice win.
The time complexity is O(n) due to the linear examination of the string, with constant space use at O(1).
If the number of '?' is odd, Alice will definitely win because she can choose to replace the last '?' with any digit, making the sum of the first half different from the sum of the second half.
If the number of '?' is even, Alice will try to make the sums of the two halves different by placing 9 in the half with the larger current sum and 0 in the half with the smaller current sum. Bob, on the other hand, will try to make the sums equal by placing a digit in the other half that matches the digit Alice placed.
As a result, all remaining even-numbered '?' will be concentrated in one half. Suppose the current difference between the sums of the two halves is d.
Let's consider the case where there are two remaining '?' and the difference is x:
x \lt 9, Alice will definitely win because she can replace one of the '?' with 9, making the sums of the two halves different.x \gt 9, Alice will definitely win because she can replace one of the '?' with 0, making the sums of the two halves different.x = 9, Bob will definitely win. Suppose Alice replaces a digit with a, then Bob can replace the other '?' with 9 - a, making the sums of the two halves equal.Therefore, if the difference between the sums of the two halves is d = \frac{9 times cnt}{2}, where cnt is the number of remaining '?', Bob will definitely win; otherwise, Alice will definitely win.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Count '?' and Digits in Each Half | The time complexity is O(n) since we need to traverse the string once to gather necessary information, and the space complexity is O(1) because we are using a constant amount of extra space. |
| Game Theory Optimized Detection | The time complexity is O(n) due to the linear examination of the string, with constant space use at O(1). |
| Case Analysis | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count '?' and Digit Sums | O(n) | O(1) | General solution; simple single-pass counting and arithmetic reasoning |
| Game Theory Optimized Detection | O(n) | O(1) | When analyzing optimal play and parity logic in interview game problems |
LeetCode 1927. Sum Game • Happy Coding • 2,189 views views
Watch 4 more video solutions →Practice Sum Game with our built-in code editor and test cases.
Practice on FleetCode