In Sum Game, Alice and Bob alternately replace '?' in a string of digits. The winner is determined by whether the first half and second half sums can be equal after all moves. Use greedy choices to maximize advantage while validating sum invariants to predict if Alice can guarantee a win.
Problem Statement
Alice and Bob play a game starting with Alice. You are given a string num of even length containing digits and '?' characters. On each turn, the current player replaces one '?' with a digit from 0 to 9.
The game ends when no '?' remain. Alice wins if the sum of the first half differs from the sum of the second half. Otherwise, Bob wins. Determine if Alice can guarantee a win assuming both play optimally.
Examples
Example 1
Input: num = "5023"
Output: false
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
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
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 <= 105
- num.length is even.
- num consists of only digits and '?'.
Solution Approach
Calculate current sums and unknowns
Split num into two halves. Count sum of digits and number of '?' in each half. This provides the initial state for invariant validation and greedy analysis.
Apply greedy replacement strategy
Alice should always replace a '?' to maximize the sum difference in her favor, while Bob aims to balance sums. Consider the effect of each replacement on the sum modulo 9 to anticipate final outcomes.
Evaluate invariant to predict winner
After all replacements, use the formula comparing weighted sums and remaining '?' contributions. If Alice can force the difference to be nonzero, she wins. Otherwise, Bob can always counter to equalize sums.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) since each character is processed once to compute sums and count '?'. Space complexity is O(1) beyond input storage as only counters are used.
What Interviewers Usually Probe
- Looking for correct sum tracking and handling of '?'
- Expect insight into greedy strategy and modular reasoning
- Checking ability to predict outcome before simulating all moves
Common Pitfalls or Variants
Common pitfalls
- Forgetting to consider distribution of '?' between halves
- Assuming Alice can always pick optimal digits without considering Bob's counters
- Neglecting modulo arithmetic leading to wrong winner prediction
Follow-up variants
- Sum Game with odd length strings requiring extra rules
- Allow '?' to be replaced with digits outside 0-9 range
- Multiple players alternating instead of just Alice and Bob
How GhostInterview Helps
- Provides step-by-step sum and '?' counting guidance
- Highlights greedy choices and modular checks to predict outcome
- Simulates key scenarios to show why Alice can or cannot win
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy to solve Sum Game?
Use a greedy approach to replace '?' and maintain invariant checks on the sums of each half to determine if Alice can win.
Why do we consider modulo 9 in Sum Game?
Modulo 9 captures the effect of digit replacements on the sum difference efficiently and predicts if Bob can always balance the halves.
How do '?' positions affect the game outcome?
The number and location of '?' in each half determine if Alice can force a sum difference or if Bob can always counter to equalize sums.
Can Alice always win if she starts first?
No, Alice can only guarantee a win if the combination of '?' distribution and existing sums allows her greedy moves to unbalance the halves.
What pattern does Sum Game exemplify?
It demonstrates the greedy choice plus invariant validation pattern, where optimal local choices and sum invariants predict the winner.
Need direct help with Sum Game instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Sum Game from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Alice and Bob play a game removing colored pieces; Alice wins if she makes the last valid move.
Open problem page#1903 Largest Odd Number in StringFind the largest odd number in a string using a greedy approach with careful digit inspection and invariant checks.
Open problem page#2029 Stone Game IXIn the Stone Game IX problem, Alice and Bob take turns removing stones, and Alice wins if the sum of removed stones is divisible by 3.
Open problem page