Code Implementation

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        sum1 = sum2 = cnt1 = cnt2 = 0
        for i in range(n):
            if i & 1 == 0:
                if num[i] == '?':
                    cnt1 += 1
                else:
                    sum1 += int(num[i])
            else:
                if num[i] == '?':
                    cnt2 += 1
                else:
                    sum2 += int(num[i])
        # If number of question marks is odd, Alice can always win
        if (cnt1 + cnt2) % 2 == 1:
            return True
        # Otherwise, check if Alice can force a win
        diff = sum1 - sum2
        # Each ? in left/right can be replaced by 0~9, but their sum difference matters
        # Alice moves first, so she can always maximize the difference
        # If (cnt1 - cnt2) * 9 // 2 != diff, then Alice can win
        return diff != (cnt2 - cnt1) * 9 // 2
      

class Solution {
public:
    bool sumGame(string num) {
        int n = num.size();
        int sum1 = 0, sum2 = 0, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                if (num[i] == '?') cnt1++;
                else sum1 += num[i] - '0';
            } else {
                if (num[i] == '?') cnt2++;
                else sum2 += num[i] - '0';
            }
        }
        if ((cnt1 + cnt2) % 2 == 1) return true;
        int diff = sum1 - sum2;
        return diff != (cnt2 - cnt1) * 9 / 2;
    }
};
      

class Solution {
    public boolean sumGame(String num) {
        int n = num.length();
        int sum1 = 0, sum2 = 0, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                if (num.charAt(i) == '?') cnt1++;
                else sum1 += num.charAt(i) - '0';
            } else {
                if (num.charAt(i) == '?') cnt2++;
                else sum2 += num.charAt(i) - '0';
            }
        }
        if ((cnt1 + cnt2) % 2 == 1) return true;
        int diff = sum1 - sum2;
        return diff != (cnt2 - cnt1) * 9 / 2;
    }
}
      

var sumGame = function(num) {
    let n = num.length;
    let sum1 = 0, sum2 = 0, cnt1 = 0, cnt2 = 0;
    for (let i = 0; i < n; ++i) {
        if (i % 2 === 0) {
            if (num[i] === '?') cnt1++;
            else sum1 += parseInt(num[i]);
        } else {
            if (num[i] === '?') cnt2++;
            else sum2 += parseInt(num[i]);
        }
    }
    if ((cnt1 + cnt2) % 2 === 1) return true;
    let diff = sum1 - sum2;
    return diff !== (cnt2 - cnt1) * 9 / 2;
};
      

Problem Description

You are given a string num consisting of an even number of digits and question marks ('?'). The string represents a number split into two equal halves. Alice and Bob take turns replacing a question mark with a digit from 0 to 9, with Alice going first. Once all question marks are replaced, if the sum of the digits in the first half equals the sum in the second half, Bob wins. Otherwise, Alice wins. Both players play optimally.

Key constraints:

• The input num is always of even length.
• Each player must replace one question mark per turn, and cannot reuse digits or change already set digits.
• There is always at least one question mark.
• Return true if Alice wins, false if Bob wins.

Thought Process

The first step is to recognize that this is a two-player game with optimal play. At first glance, it might seem necessary to simulate every possible move, but this quickly becomes infeasible due to the exponential number of choices for each question mark.

Instead, we can focus on the sums of each half and the number of question marks in each half. Since each player picks digits optimally, Alice will maximize the difference between the two halves, while Bob will try to minimize it. The key is to determine whether Alice can always force the sums to be unequal, regardless of Bob's actions.

By observing the structure, we see that the two halves can be analyzed separately: count the sum of known digits and the number of question marks in each half. The outcome depends on whether the difference in possible sums can be balanced, given the number of question marks and the order of play.

Solution Approach

• Step 1: Iterate through the input string num and for each half, count:
  • The sum of known digits (for both halves).
  • The number of question marks (for both halves).
• Step 2: If the total number of question marks is odd, Alice will always win. This is because she will have one extra move and can always make the sums unequal.
• Step 3: If the number of question marks is even, compare the maximum possible difference Alice can create with the difference in known digit sums.
  • Each question mark can be replaced with any digit from 0 to 9, so the sum difference can be maximized by choosing 9 for one side and 0 for the other.
  • For each unmatched question mark between halves, Alice can maximize the difference by choosing 9 for her side and Bob can minimize by choosing 0 for his side.
  • The formula for the maximum difference is (cnt2 - cnt1) * 9 / 2, where cnt1 and cnt2 are the number of question marks in each half.
  • If the actual difference in known digit sums does not match the maximum possible difference, Alice can force a win.
• Step 4: Return True if Alice can win, otherwise False.

This approach avoids brute-force simulation and instead leverages mathematical reasoning about the sums and question mark distribution.

Example Walkthrough

Example Input: num = "2?9??0"

• Split into halves: "2?9" and "??0"
• First half ("2?9"): sum = 2 + 9 = 11, question marks = 1
• Second half ("??0"): sum = 0, question marks = 2
• Total question marks = 3 (odd)
• Since the total is odd, Alice has an extra move and can always force the sums to be unequal, so Alice wins.

Another Example: num = "?329?6"

• Split into halves: "?32" and "9?6"
• First half: sum = 3 + 2 = 5, question marks = 1
• Second half: sum = 9 + 6 = 15, question marks = 1
• Total question marks = 2 (even)
• Difference in sums: 5 - 15 = -10
• Difference in question marks: 1 - 1 = 0
• Maximum possible difference is 0, so if the difference in sums is not 0, Alice wins. Here, -10 != 0, so Alice wins.

Time and Space Complexity

• Brute-force approach: Would try every possible digit for every question mark, leading to O(10^k) time where k is the number of question marks. This is not feasible for large inputs.
• Optimized approach: Only a single pass through the string is needed to compute sums and question mark counts, so the time complexity is O(n), where n is the length of num.
• Space complexity: Only a few integer variables are used, so the space complexity is O(1).

Summary

The Sum Game problem can be solved efficiently by analyzing the distribution of question marks and the sums of known digits in each half. By recognizing that the game reduces to a matter of maximizing or minimizing the sum difference with optimal play, we avoid brute-force simulation and achieve a linear time solution. The key insight is that Alice can always win if the total number of question marks is odd, or if the difference in known digit sums cannot be balanced by the available question marks. This makes the solution both elegant and efficient.