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.
This approach bypasses simulating the game entirely and instead uses a mathematical formula to determine the winner directly. The key insight is that the game is determined by the initial difference in sums and the distribution of question marks. With optimal play from both sides, the final difference can be calculated, and we can check if it's possible for it to be zero.
Algorithm
- First, make a single pass through the string to compute the sum of existing digits and the count of
?characters for the left and right halves. Let them besumLeft,sumRight,qLeft, andqRight. - Calculate the initial difference in sums:
sumDiff = sumLeft - sumRight. - Calculate the difference in the number of
?s:qDiff = qLeft - qRight. - The total number of turns is
qLeft + qRight. If this number is odd, Alice gets one more turn than Bob, including the very last turn. With the last move, she can always ensure the sums are not equal (out of 10 possible digits, at most one can make the sums equal). Therefore, ifqLeft + qRightis odd, Alice wins. - If
qLeft + qRightis even, both players have an equal number of moves. The game's outcome depends on whether Bob can perfectly balance the contributions from the?s to offset the initialsumDiff. - It can be shown through analysis of optimal strategies that the total change in the sum difference contributed by filling all
?s will be exactly9 * (qLeft - qRight) / 2if Alice tries to increasesumLeftand Bob tries to decrease it (or vice-versa). - Bob wins if and only if the initial difference can be perfectly canceled out by the changes from filling
?s. The condition for Bob to win is:sumDiff + 9 * qDiff / 2 = 0. - If this condition is met, Bob wins (return
false). Otherwise, Alice wins (returntrue).
Walkthrough
The problem can be solved by analyzing the game theory behind optimal play without simulating the turns.
-
Initial State: We first parse the string to find the sum of digits and count of
?s on both halves. Let's denote themsumLeft,sumRight,qLeft,qRight. -
Odd Number of
?s: If the total number of question marks,qLeft + qRight, is odd, Alice gets the last turn. On her final move, she can choose from 10 digits. At most one of these digits will make the two sums equal. Since she can choose any of the other 9 digits, she can always ensure the sums are unequal. Thus, if the total?count is odd, Alice wins. -
Even Number of
?s: IfqLeft + qRightis even, Alice and Bob have an equal number of turns,k = (qLeft + qRight) / 2. Let's analyze the net effect of their moves on the differenced = sumLeft - sumRight.- Alice wants to maximize
|d|. Bob wants to maked=0. - Regardless of whose sum is initially larger, one player will be trying to increase the difference
sumLeft - sumRightand the other will be trying to decrease it. For instance, ifsumLeft > sumRight, Alice will try to increase the difference by placing9s in the left half, while Bob will try to decrease it by placing9s in the right half. - It can be proven that with optimal play, the total change in the difference
sumLeft - sumRightcaused by filling all the?s is exactly9 * (qLeft - qRight) / 2. - Therefore, the final difference will be
(sumLeft - sumRight) + 9 * (qLeft - qRight) / 2. - Bob wins if this final difference is zero. This gives us the winning condition for Bob:
sumLeft - sumRight + 9 * (qLeft - qRight) / 2 = 0This simplifies to2 * (sumLeft - sumRight) + 9 * (qLeft - qRight) == 0.
- Alice wants to maximize
If this equation holds, Bob can always force a draw, so he wins. Otherwise, Alice can always ensure the sums are not equal, and she wins.
class Solution { public boolean sumGame(String num) { int n = num.length(); int qLeft = 0, qRight = 0; int sumLeft = 0, sumRight = 0; // Calculate sums and '?' counts for the left half for (int i = 0; i < n / 2; i++) { if (num.charAt(i) == '?') { qLeft++; } else { sumLeft += num.charAt(i) - '0'; } } // Calculate sums and '?' counts for the right half for (int i = n / 2; i < n; i++) { if (num.charAt(i) == '?') { qRight++; } else { sumRight += num.charAt(i) - '0'; } } int totalQ = qLeft + qRight; // If total '?' is odd, Alice has the last move and will always win. if (totalQ % 2 != 0) { return true; } // If total '?' is even, Bob wins if he can balance the sums. // The condition is 2 * (sumLeft - sumRight) == 9 * (qRight - qLeft). // Which is equivalent to 2 * (sumLeft - sumRight) + 9 * (qLeft - qRight) == 0. int sumDiff = sumLeft - sumRight; int qDiff = qLeft - qRight; if (2 * sumDiff + 9 * qDiff == 0) { return false; // Bob wins } else { return true; // Alice wins } }}Complexity
Time
O(N) - The algorithm involves a single loop through the string of length N.
Space
O(1) - Only a few integer variables are needed to store the sums and counts.
Trade-offs
Pros
Extremely efficient, requiring only a single pass over the input string.
The logic is concise and avoids complex simulation.
Constant space complexity.
Cons
The derivation of the final formula is non-trivial and requires careful game theory reasoning, making it less intuitive to come up with during a contest.
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; }}class Solution { public: bool sumGame ( string num ) { int n = num . size (); int cnt1 = 0 , cnt2 = 0 ; int s1 = 0 , s2 = 0 ; for ( int i = 0 ; i < n / 2 ; ++ i ) { if ( num [ i ] == '?' ) { cnt1 ++ ; } else { s1 += num [ i ] - '0' ; } } for ( int i = n / 2 ; i < n ; ++ i ) { if ( num [ i ] == '?' ) { cnt2 ++ ; } else { s2 += num [ i ] - '0' ; } } return ( cnt1 + cnt2 ) % 2 == 1 || ( s1 - s2 ) != 9 * ( cnt2 - cnt1 ) / 2 ; } };class Solution: def sumGame(self, num: str) -> bool: n = len(num) cnt1 = num[: n // 2]. count("?") cnt2 = num[n // 2:]. count("?") s1 = sum(int(x) for x in num[: n // 2] if x != "?") s2 = sum(int(x) for x in num[n // 2:] if x != "?") return (cnt1 + cnt2) % 2 == 1 or s1 - s2 != 9 * (cnt2 - cnt1) // 2Video 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.