2039 Sum Game
2039 Sum Game
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:
1
2
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.
1
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.
Example 1:
1
2
3
4
5
6
**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:
1
2
3
4
5
**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:
1
2
3
4
5
6
7
8
9
10
**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.
Constraints:
1
2
3
2 <= num.length <= 105
num.length is **even**.
num consists of only digits and '?'.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution:
def sumGame(self, num: str) -> bool:
half_length = int(len(num)/2) # len is always even
count_of_unknowns_left = 0
count_of_unknowns_right = 0
count_of_unknown = -1
for k in num[:half_length]:
if k == "?":
count_of_unknowns_left = count_of_unknowns_left + 1
for k in num[half_length:]:
if k == "?":
count_of_unknowns_right = count_of_unknowns_right + 1
diff_sum = -1
lhs = self.calculate_sum(num[:half_length])
rhs = self.calculate_sum(num[half_length:])
if lhs == rhs and count_of_unknowns_right == count_of_unknowns_left:
return False #bob wins
if abs(count_of_unknowns_right - count_of_unknowns_left) % 2 == 1:
return True # alice always wins
if lhs > rhs and count_of_unknowns_right > count_of_unknowns_left:
diff_sum = lhs-rhs
count_of_unknown = count_of_unknowns_right - count_of_unknowns_left
if lhs < rhs and count_of_unknowns_right < count_of_unknowns_left:
diff_sum = rhs-lhs
count_of_unknown = count_of_unknowns_left - count_of_unknowns_right
print(diff_sum, count_of_unknown)
if diff_sum > 0 and count_of_unknown > 0:
return int((count_of_unknown + 1)/2) * 9 > diff_sum or int((count_of_unknown)/2) * 9 < diff_sum# >= for 9? test case
return True # alice always wins
def calculate_sum(self, nums : str) -> int:
print(nums)
sum = 0
for k in nums:
if k != "?":
sum = sum + int(k)
return sum
#?329 5???
#14 = 2?
#x + y = 14
#sum(x) + sum(y) = k
#sum(x) > k // alice wins
#sum(x) < k for all x between 0 to 9 then bob wins
#num+1/2
This post is licensed under CC BY 4.0 by the author.