Sum Game
MedPrompt
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:
- Choose an index
iwherenum[i] == '?'. - Replace
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.
- For example, if the game ended with
num = "243801", then Bob wins because2+4+3 = 8+0+1. If the game ended withnum = "243803", then Alice wins because2+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.lengthis even.numconsists of only digits and'?'.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves simulating the game turn by turn. We first calculate the initial sums and the number of question marks on each half. Then, we loop for as many turns as there are question marks. In each turn, the current player makes a greedy, optimal move. Alice tries to maximize the difference between the sums, while Bob tries to minimize it. After the simulation finishes, we check if the sums are equal to determine the winner.
Algorithm
- First, iterate through the string to calculate the initial sum of digits and the count of
?characters for both the left and right halves of the string. Let these besumLeft,sumRight,qLeft, andqRight. - The total number of turns in the game is
qLeft + qRight. Alice moves first. - We can simulate the game turn by turn, assuming both players play optimally. The simulation runs for
qLeft + qRightturns. - In each turn, we determine the current player's best move. A player's goal is to either maximize (Alice) or minimize (Bob) the final difference
sumLeft - sumRight. - Alice's Optimal Move: To maximize the final difference, she wants to make
sumLeftas large as possible andsumRightas small as possible. On her turn, she will choose to place a9in a?on the side that is currently smaller or equal, or a9on the side that is already larger to increase her lead. A simpler optimal strategy that achieves the same goal is to always try to increase the difference in her favor. IfsumLeft >= sumRight, she will try to place a9in the left half. If she can't, she'll place a0in the right half. IfsumLeft < sumRight, she'll place a9in the right half. - Bob's Optimal Move: To make the final difference zero, he will try to counter Alice's moves. If
sumLeft > sumRight, he will try to place a9in the right half to reduce the gap. If he can't, he'll place a0in the left half. IfsumLeft < sumRight, he'll place a9in the left half. - The simulation proceeds turn by turn, updating the sums and
?counts. - After all
?s are filled, ifsumLeft == sumRight, Bob wins. Otherwise, Alice wins.
Walkthrough
The core idea is to model the game directly. We keep track of the current sums and the remaining question marks for both halves. The game proceeds in turns, starting with Alice.
Let's define the optimal greedy strategy:
- Alice: Wants to make the final sums unequal. She will always make a move that pushes the sums further apart. If the left sum is greater than or equal to the right sum, she will place a '9' in a left-half
?if available. If not, she must play on the right, and to minimize helping Bob, she places a '0'. The logic is reversed if the right sum is initially greater. - Bob: Wants to make the final sums equal. He will always try to make the sums closer. If the left sum is greater than the right, he will place a '9' in a right-half
?if available to close the gap. If not, he must play on the left, and to minimize the damage, he places a '0'.
We can run a loop for qLeft + qRight turns, alternating between Alice and Bob, and applying their optimal move based on the current state of the sums and available ?s. Finally, we compare the sums.
class Solution { public boolean sumGame(String num) { int n = num.length(); int qLeft = 0, qRight = 0; double sumLeft = 0, sumRight = 0; for (int i = 0; i < n / 2; i++) { if (num.charAt(i) == '?') { qLeft++; } else { sumLeft += num.charAt(i) - '0'; } } for (int i = n / 2; i < n; i++) { if (num.charAt(i) == '?') { qRight++; } else { sumRight += num.charAt(i) - '0'; } } int totalQ = qLeft + qRight; // Alice moves on odd turns (1, 3, ...), Bob on even turns (2, 4, ...) for (int turn = 1; turn <= totalQ; turn++) { if (turn % 2 != 0) { // Alice's turn if (sumLeft < sumRight) { if (qLeft > 0) { sumLeft += 9; qLeft--; } else { // Must play on the right, play 0 to not increase sumRight qRight--; } } else { // sumLeft >= sumRight if (qRight > 0) { sumRight += 9; qRight--; } else { // Must play on the left, play 0 to not increase sumLeft qLeft--; } } } else { // Bob's turn if (sumLeft < sumRight) { if (qRight > 0) { sumRight += 0; qRight--; } else { sumLeft += 9; qLeft--; } } else { // sumLeft >= sumRight if (qLeft > 0) { sumLeft += 0; qLeft--; } else { sumRight += 9; qRight--; } } } } return sumLeft != sumRight; }}Note: The provided simulation logic is one interpretation of optimal play. A simpler greedy strategy based on initial sums also works and leads to the mathematical approach.
Complexity
Time
O(N) - We make one pass to get initial counts (O(N)) and then a second loop that runs for at most N turns. The total time is proportional to the length of the string.
Space
O(1) - We only use a few variables to store sums and counts.
Trade-offs
Pros
More intuitive than the purely mathematical approach as it directly models the game.
Correctly solves the problem if the greedy logic is sound.
Cons
The logic for optimal play in each step of the simulation can be complex to get right, especially handling the case where sums are equal.
While having the same O(N) time complexity as the mathematical approach, it involves a loop that runs up to N times after the initial pass, making it less efficient in practice due to higher constant factors and more operations.
Solutions
Solution
class Solution {public boolean sumGame(String num) { int n = num.length(); int cnt1 = 0, cnt2 = 0; int s1 = 0, s2 = 0; for (int i = 0; i < n / 2; ++i) { if (num.charAt(i) == '?') { cnt1++; } else { s1 += num.charAt(i) - '0'; } } for (int i = n / 2; i < n; ++i) { if (num.charAt(i) == '?') { cnt2++; } else { s2 += num.charAt(i) - '0'; } } return (cnt1 + cnt2) % 2 == 1 || s1 - s2 != 9 * (cnt2 - cnt1) / 2; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.