#1927
Sum Game
specialist · 890 · lc medium +31 · verified · 49.6% accepted · 542 likes · top 37%
Description
Alice and Bob alternate turns (Alice first) filling each '?' in a string num of even length with any digit '0'–'9'. Bob wins if the sum of digits in the first half equals the sum in the second half; Alice wins otherwise.
Both play optimally. Return true if Alice wins, false if Bob wins.
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.
Code
1
2
3