Sum Game
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.
Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.
Example 1
Input
num = "5023"Output
falseThere are no moves to be made, and the sum of the first half equals the sum of the second half: 5 + 0 = 2 + 3.
Example 2
Input
num = "25??"Output
trueAlice can replace one of the '?'s with '9' and it will be impossible for Bob to make the sums equal.
Constraints
- 2 <= num.length <= 10^5
- num.length is even.
- num consists of only digits and '?'.