Problem Description

Alice and Bob play a turn-based game with a string num of even length containing digits and '?' characters. Alice goes first.

On each turn, a player must:

1. Find an index i where num[i] == '?'
2. Replace that '?' with any digit from '0' to '9'

The game continues until all '?' characters are replaced with digits.

Winning conditions:

• Bob wins if the sum of digits in the first half equals the sum of digits in the second half
• Alice wins if these sums are not equal

For example:

• If the final string is "243801", Bob wins because 2+4+3 = 8+0+1 = 9
• If the final string is "243803", Alice wins because 2+4+3 = 9 but 8+0+3 = 11

The problem asks you to determine who wins when both players play optimally. Return true if Alice wins, false if Bob wins.

Key insights for the solution:

The winner depends on two factors:

1. The parity of total '?' characters - if odd, Alice always wins since she gets the last move
2. The relationship between the initial sum difference and the distribution of '?' characters

When there's an even number of '?' characters, Alice tries to maximize the difference between halves (placing 9 in the larger sum half, 0 in the smaller), while Bob tries to balance them. The game ultimately comes down to whether the initial sum difference equals exactly 9 × (cnt2 - cnt1) / 2, where cnt1 and cnt2 are the counts of '?' in each half. Bob wins only when this exact equality holds; otherwise, Alice wins.

Intuition

Let's think about what each player wants to achieve. Alice wants the two halves to have different sums, while Bob wants them to be equal. Since both play optimally, we need to analyze their strategies.

First, consider the simplest case: if there's an odd number of '?' characters total, Alice gets the last move. No matter what Bob does before, Alice can always make the final replacement to ensure the sums are unequal. So Alice wins immediately in this case.

Now for the more interesting even number case. Let's think about optimal play:

• When Alice sees a '?', she wants to maximize the difference between halves
• When Bob sees a '?', he wants to minimize this difference

If Alice places a digit in one half, Bob's best response is to place a digit in the opposite half to counterbalance. For example, if Alice puts 9 in the left half (increasing its sum), Bob will put 9 in the right half to maintain balance.

But here's the key insight: Alice can force all remaining '?' characters to end up in the same half! How? By always choosing '?' from the half that currently has the smaller sum. This forces Bob to respond in the opposite half. After several rounds of this, all '?' will be concentrated in one half.

Once all '?' are in one half, the game becomes deterministic. Let's say we have k question marks all in one half, and the current difference between halves is d. Alice and Bob will alternate filling these k positions. Alice will try to maximize (using 9) or minimize (using 0) based on which half has the '?'. Bob will try to keep things balanced.

Through this alternating play, Alice effectively adds 9 each turn while Bob adds 0, or vice versa. The net effect over k turns (where k is even) is that the sum changes by exactly 9 × k/2.

Therefore, Bob can only win if the initial difference d can be exactly compensated by this 9 × k/2 change. Specifically, if s1 - s2 = 9 × (cnt2 - cnt1) / 2, where cnt1 and cnt2 are the number of '?' in each half, then Bob wins. Any other value means Alice can prevent equality, so Alice wins.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows directly from our analysis of the game theory. We need to check two conditions to determine if Alice wins:

1. Count the question marks in each half:

   • Split the string at the midpoint (n // 2)
   • Count '?' in the first half as cnt1
   • Count '?' in the second half as cnt2

2. Calculate the current sum of known digits in each half:

   • Sum all numeric digits (excluding '?') in the first half as s1
   • Sum all numeric digits (excluding '?') in the second half as s2

3. Apply the winning conditions:

   • Condition 1: If (cnt1 + cnt2) % 2 == 1, Alice wins immediately (odd number of '?' means Alice gets the last move)
   • Condition 2: If the total '?' count is even, check if s1 - s2 != 9 * (cnt2 - cnt1) // 2
     • Bob wins only when s1 - s2 == 9 * (cnt2 - cnt1) // 2 (exact balance possible)
     • Alice wins in all other cases

The formula 9 * (cnt2 - cnt1) // 2 represents the net effect on the sum difference when:

• If cnt2 > cnt1: More '?' in the second half means the second half's sum will increase relative to the first
• If cnt1 > cnt2: More '?' in the first half means the first half's sum will increase relative to the second
• The factor of 9/2 comes from Alice and Bob alternating between placing 9 and 0 optimally

The solution returns True if either condition for Alice's victory is met, False otherwise (meaning Bob wins).

This approach runs in O(n) time where n is the length of the string, as we traverse the string once to count '?' characters and calculate sums. The space complexity is O(1) as we only use a few variables to store counts and sums.

Example Walkthrough

Let's walk through the solution with the string num = "?3295?".

Step 1: Split and analyze the string

• String length: 6 (even length)
• First half: "?32" (indices 0-2)
• Second half: "95?" (indices 3-5)

Step 2: Count question marks in each half

• cnt1 (first half): 1 question mark
• cnt2 (second half): 1 question mark
• Total question marks: 2 (even number)

Step 3: Calculate current sums (excluding '?')

• s1 (first half): 3 + 2 = 5
• s2 (second half): 9 + 5 = 14

Step 4: Check winning conditions

Condition 1: Is the total number of '?' odd?

• (1 + 1) % 2 = 0, so NO - we need to check condition 2

Condition 2: Check if s1 - s2 == 9 × (cnt2 - cnt1) / 2

• Left side: s1 - s2 = 5 - 14 = -9
• Right side: 9 × (1 - 1) / 2 = 9 × 0 / 2 = 0
• Since -9 ≠ 0, the equality doesn't hold

Result: Alice wins (returns true)

Understanding the gameplay: With optimal play:

• Alice goes first and chooses the '?' in position 0. She wants to maximize the difference, so she checks which half currently has a smaller sum. The first half (5) is smaller than the second (14), so she places '0' to keep it small.
• Bob's turn: He chooses the '?' in position 5. To balance Alice's move, he places '0' as well.
• Final string: "032950"
• First half sum: 0 + 3 + 2 = 5
• Second half sum: 9 + 5 + 0 = 14
• The sums are different (5 ≠ 14), so Alice wins!

Note that Bob needed the initial difference (-9) to exactly match what he could compensate for with the question marks (which was 0 in this case since cnt1 = cnt2). Since it didn't match, Alice could maintain the inequality.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string. This is because:

• The slicing operations num[: n // 2] and num[n // 2 :] each take O(n/2) time
• The count("?") method on each half iterates through n/2 characters, taking O(n/2) time for each call
• The sum comprehensions iterate through each half of the string once, processing n/2 characters each, resulting in O(n/2) time for each sum operation
• All these operations are performed sequentially, giving us O(n/2) + O(n/2) + O(n/2) + O(n/2) = O(n) total time

The space complexity is O(1). This is because:

• The slicing operations in Python create new string objects, but since we're only using them temporarily for counting and summing (not storing them), and the intermediate results are just integer values (cnt1, cnt2, s1, s2)
• Only a constant amount of extra space is used for the integer variables regardless of the input size
• The comprehensions don't create intermediate lists since they're used directly in the sum() function as generator expressions

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division vs Float Division

A critical pitfall is using float division (/) instead of integer division (//) when calculating 9 * question_mark_difference // 2.

Why it's problematic:

• Using 9 * question_mark_difference / 2 produces a float (e.g., 4.5)
• Comparing a float with an integer sum difference can lead to incorrect results
• When question_mark_difference is odd, the result should be non-integer, making exact equality impossible (which is correct for Alice to win)

Incorrect:

# This can cause wrong answers due to float comparison
return sum_difference != 9 * question_mark_difference / 2

Correct:

# Integer division ensures proper comparison
return sum_difference != 9 * question_mark_difference // 2

2. Misunderstanding the Question Mark Difference Direction

Another common mistake is calculating the question mark difference incorrectly as cnt1 - cnt2 instead of cnt2 - cnt1.

Why it matters:

• The formula represents how much the second half can gain relative to the first half
• If there are more ? in the second half (cnt2 > cnt1), the second half has more potential to increase
• Reversing this subtraction flips the sign and produces wrong results

Incorrect:

# Wrong direction - this inverts the logic
question_mark_difference = question_marks_first_half - question_marks_second_half

Correct:

# Correct: second half minus first half
question_mark_difference = question_marks_second_half - question_marks_first_half

3. Forgetting to Handle Non-Digit Characters When Calculating Sums

Attempting to convert '?' characters to integers will cause a runtime error.

Incorrect:

# This will crash when encountering '?'
sum_first_half = sum(int(digit) for digit in first_half)

Correct:

# Filter out '?' characters before converting to int
sum_first_half = sum(int(digit) for digit in first_half if digit != "?")

4. Misunderstanding Win Conditions

A subtle pitfall is inverting the win condition logic - thinking Alice wins when the sums CAN be made equal rather than when they CANNOT.

Remember:

• Bob wins ONLY when sums can be made exactly equal
• Alice wins in ALL other cases (including when total ? is odd)
• The condition should check for inequality (!=), not equality (==)