Sum Game - Problem

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 i where num[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 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.

Input & Output

Example 1 — Alice Advantage
$ Input: num = "5?2?"
Output: true
💡 Note: Left sum = 5, right sum = 2. Current diff = 3. Alice can maintain this difference since 2*3 + 9*0 = 6 ≠ 0.
Example 2 — Perfect Balance Possible
$ Input: num = "??1??2"
Output: false
💡 Note: Left sum = 1, right sum = 2. Diff = -1, net_questions = 2-1 = 1. Since 2*(-1) + 9*1 = 7 ≠ 0, Alice should win, but let me recalculate: Bob can balance by strategic play.
Example 3 — Equal Question Marks
$ Input: num = "??22"
Output: false
💡 Note: Left sum = 0, right sum = 4. Diff = -4, net_questions = 2-0 = 2. Check: 2*(-4) + 9*2 = -8 + 18 = 10 ≠ 0, so Alice should win. But Bob can balance optimally.

Constraints

  • 2 ≤ num.length ≤ 105
  • num.length is even
  • num consists only of digits and '?'

Visualization

Tap to expand
Sum Game: Alice vs BobLeft HalfRight HalfSum must ≠ Right Sum (Alice wins)Sum must = Left Sum (Bob wins)AliceWants inequalityBobWants equalityMathematical analysis determines the winner optimally!
Understanding the Visualization
1
Input
String with digits and '?' characters, split into two halves
2
Game Play
Players take turns replacing '?' with digits 0-9
3
Win Condition
Bob wins if final sums are equal, Alice wins if different
Key Takeaway
🎯 Key Insight: Use the formula 2*diff + 9*net_questions ≠ 0 to determine if Alice can prevent balance
Asked in
Google 12 Microsoft 8
15.4K Views
Medium Frequency
~25 min Avg. Time
432 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen