Decide the Winner of a Digit-Balance Game
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Alice and Bob alternately replace one `?` in the even-length string `num` with any digit from 0 through 9. Alice moves first. When no question marks remain, Bob wins if the digit sums of the two halves are equal; otherwise Alice wins. Assuming optimal play, return whether Alice can force a win. Either player may choose a question mark in either half.
```cpp
class Solution {
public:
bool sumGame(string num);
};
```
### Examples
**Example 1:**
```text
num = "1?1?"
Output: false
Explanation: Bob copies Alice's digit into the other half, keeping the two totals equal.
```
**Example 2:**
```text
num = "00??"
Output: true
Explanation: Alice places 9 in the right half, whose final sum is then positive regardless of Bob's move.
```
### Constraints
- `2 <= num.length <= 10^5`; the length is even.
- Each character is a decimal digit or a question mark.
### Clarifying Questions
If no question marks exist, compare the current sums. Players may choose a question mark in either half.
```hint Inspect the structure
Center each unfilled position at 4.5: how much can one move change the signed balance?
```
### Reasoning checkpoints
- Prove the outcome against optimal replies for both players, rather than for just one possible completed string.
- Handle unequal numbers of unknown positions in the two halves and the case with no moves remaining.
### Optional extensions
How would the strategy change if replacement digits ranged from 0 through B?
Overview: Decide the Winner of a Digit-Balance Game. Two players alternately replace one question mark in the even-length string num with a digit from 0 through 9. Alice moves first and wants the sums of the two halves to differ after all replacements. Bob wants equality. Both choose optimally. Return true exactly when Alice can force a win.
