# Sum Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-game)
Canonical: https://scaleengineer.com/dsa/problems/sum-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** String
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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. Choose an index `i` where `num[i] == '?'`.
2. 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**.

* 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:**

**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.

**Constraints:**

* `2 <= num.length <= 105`
* `num.length` is **even**.
* `num` consists of only digits and `'?'`.

# Approaches
## Greedy Simulation
This approach involves simulating the game turn by turn. We first calculate the initial sums and the number of question marks on each half. Then, we loop for as many turns as there are question marks. In each turn, the current player makes a greedy, optimal move. Alice tries to maximize the difference between the sums, while Bob tries to minimize it. After the simulation finishes, we check if the sums are equal to determine the winner.
**Time:** O(N) - We make one pass to get initial counts (O(N)) and then a second loop that runs for at most N turns. The total time is proportional to the length of the string. · **Space:** O(1) - We only use a few variables to store sums and counts.
**Pros:** More intuitive than the purely mathematical approach as it directly models the game.; Correctly solves the problem if the greedy logic is sound.
**Cons:** The logic for optimal play in each step of the simulation can be complex to get right, especially handling the case where sums are equal.; While having the same O(N) time complexity as the mathematical approach, it involves a loop that runs up to N times after the initial pass, making it less efficient in practice due to higher constant factors and more operations.
### Explanation
The core idea is to model the game directly. We keep track of the current sums and the remaining question marks for both halves. The game proceeds in turns, starting with Alice.

Let's define the optimal greedy strategy:
- **Alice**: Wants to make the final sums unequal. She will always make a move that pushes the sums further apart. If the left sum is greater than or equal to the right sum, she will place a '9' in a left-half `?` if available. If not, she must play on the right, and to minimize helping Bob, she places a '0'. The logic is reversed if the right sum is initially greater.
- **Bob**: Wants to make the final sums equal. He will always try to make the sums closer. If the left sum is greater than the right, he will place a '9' in a right-half `?` if available to close the gap. If not, he must play on the left, and to minimize the damage, he places a '0'.

We can run a loop for `qLeft + qRight` turns, alternating between Alice and Bob, and applying their optimal move based on the current state of the sums and available `?`s. Finally, we compare the sums.

```java
class Solution {
    public boolean sumGame(String num) {
        int n = num.length();
        int qLeft = 0, qRight = 0;
        double sumLeft = 0, sumRight = 0;

        for (int i = 0; i < n / 2; i++) {
            if (num.charAt(i) == '?') {
                qLeft++;
            } else {
                sumLeft += num.charAt(i) - '0';
            }
        }

        for (int i = n / 2; i < n; i++) {
            if (num.charAt(i) == '?') {
                qRight++;
            } else {
                sumRight += num.charAt(i) - '0';
            }
        }

        int totalQ = qLeft + qRight;
        // Alice moves on odd turns (1, 3, ...), Bob on even turns (2, 4, ...)
        for (int turn = 1; turn <= totalQ; turn++) {
            if (turn % 2 != 0) { // Alice's turn
                if (sumLeft < sumRight) {
                    if (qLeft > 0) {
                        sumLeft += 9;
                        qLeft--;
                    } else {
                        // Must play on the right, play 0 to not increase sumRight
                        qRight--;
                    }
                } else { // sumLeft >= sumRight
                    if (qRight > 0) {
                        sumRight += 9;
                        qRight--;
                    } else {
                        // Must play on the left, play 0 to not increase sumLeft
                        qLeft--;
                    }
                }
            } else { // Bob's turn
                if (sumLeft < sumRight) {
                    if (qRight > 0) {
                        sumRight += 0;
                        qRight--;
                    } else {
                        sumLeft += 9;
                        qLeft--;
                    }
                } else { // sumLeft >= sumRight
                    if (qLeft > 0) {
                        sumLeft += 0;
                        qLeft--;
                    } else {
                        sumRight += 9;
                        qRight--;
                    }
                }
            }
        }

        return sumLeft != sumRight;
    }
}
```
*Note: The provided simulation logic is one interpretation of optimal play. A simpler greedy strategy based on initial sums also works and leads to the mathematical approach.*
### Algorithm
1. First, iterate through the string to calculate the initial sum of digits and the count of `?` characters for both the left and right halves of the string. Let these be `sumLeft`, `sumRight`, `qLeft`, and `qRight`.
2. The total number of turns in the game is `qLeft + qRight`. Alice moves first.
3. We can simulate the game turn by turn, assuming both players play optimally. The simulation runs for `qLeft + qRight` turns.
4. In each turn, we determine the current player's best move. A player's goal is to either maximize (Alice) or minimize (Bob) the final difference `sumLeft - sumRight`.
5. **Alice's Optimal Move**: To maximize the final difference, she wants to make `sumLeft` as large as possible and `sumRight` as small as possible. On her turn, she will choose to place a `9` in a `?` on the side that is currently smaller or equal, or a `9` on the side that is already larger to increase her lead. A simpler optimal strategy that achieves the same goal is to always try to increase the difference in her favor. If `sumLeft >= sumRight`, she will try to place a `9` in the left half. If she can't, she'll place a `0` in the right half. If `sumLeft < sumRight`, she'll place a `9` in the right half.
6. **Bob's Optimal Move**: To make the final difference zero, he will try to counter Alice's moves. If `sumLeft > sumRight`, he will try to place a `9` in the right half to reduce the gap. If he can't, he'll place a `0` in the left half. If `sumLeft < sumRight`, he'll place a `9` in the left half.
7. The simulation proceeds turn by turn, updating the sums and `?` counts.
8. After all `?`s are filled, if `sumLeft == sumRight`, Bob wins. Otherwise, Alice wins.

## Direct Mathematical Formula
This approach bypasses simulating the game entirely and instead uses a mathematical formula to determine the winner directly. The key insight is that the game is determined by the initial difference in sums and the distribution of question marks. With optimal play from both sides, the final difference can be calculated, and we can check if it's possible for it to be zero.
**Time:** O(N) - The algorithm involves a single loop through the string of length N. · **Space:** O(1) - Only a few integer variables are needed to store the sums and counts.
**Pros:** Extremely efficient, requiring only a single pass over the input string.; The logic is concise and avoids complex simulation.; Constant space complexity.
**Cons:** The derivation of the final formula is non-trivial and requires careful game theory reasoning, making it less intuitive to come up with during a contest.
### Explanation
The problem can be solved by analyzing the game theory behind optimal play without simulating the turns.

1.  **Initial State**: We first parse the string to find the sum of digits and count of `?`s on both halves. Let's denote them `sumLeft`, `sumRight`, `qLeft`, `qRight`.

2.  **Odd Number of `?`s**: If the total number of question marks, `qLeft + qRight`, is odd, Alice gets the last turn. On her final move, she can choose from 10 digits. At most one of these digits will make the two sums equal. Since she can choose any of the other 9 digits, she can always ensure the sums are unequal. Thus, if the total `?` count is odd, Alice wins.

3.  **Even Number of `?`s**: If `qLeft + qRight` is even, Alice and Bob have an equal number of turns, `k = (qLeft + qRight) / 2`. Let's analyze the net effect of their moves on the difference `d = sumLeft - sumRight`.
    - Alice wants to maximize `|d|`. Bob wants to make `d=0`.
    - Regardless of whose sum is initially larger, one player will be trying to increase the difference `sumLeft - sumRight` and the other will be trying to decrease it. For instance, if `sumLeft > sumRight`, Alice will try to increase the difference by placing `9`s in the left half, while Bob will try to decrease it by placing `9`s in the right half.
    - It can be proven that with optimal play, the total change in the difference `sumLeft - sumRight` caused by filling all the `?`s is exactly `9 * (qLeft - qRight) / 2`.
    - Therefore, the final difference will be `(sumLeft - sumRight) + 9 * (qLeft - qRight) / 2`.
    - Bob wins if this final difference is zero. This gives us the winning condition for Bob:
      `sumLeft - sumRight + 9 * (qLeft - qRight) / 2 = 0`
      This simplifies to `2 * (sumLeft - sumRight) + 9 * (qLeft - qRight) == 0`.

If this equation holds, Bob can always force a draw, so he wins. Otherwise, Alice can always ensure the sums are not equal, and she wins.

```java
class Solution {
    public boolean sumGame(String num) {
        int n = num.length();
        int qLeft = 0, qRight = 0;
        int sumLeft = 0, sumRight = 0;

        // Calculate sums and '?' counts for the left half
        for (int i = 0; i < n / 2; i++) {
            if (num.charAt(i) == '?') {
                qLeft++;
            } else {
                sumLeft += num.charAt(i) - '0';
            }
        }

        // Calculate sums and '?' counts for the right half
        for (int i = n / 2; i < n; i++) {
            if (num.charAt(i) == '?') {
                qRight++;
            } else {
                sumRight += num.charAt(i) - '0';
            }
        }

        int totalQ = qLeft + qRight;

        // If total '?' is odd, Alice has the last move and will always win.
        if (totalQ % 2 != 0) {
            return true;
        }

        // If total '?' is even, Bob wins if he can balance the sums.
        // The condition is 2 * (sumLeft - sumRight) == 9 * (qRight - qLeft).
        // Which is equivalent to 2 * (sumLeft - sumRight) + 9 * (qLeft - qRight) == 0.
        int sumDiff = sumLeft - sumRight;
        int qDiff = qLeft - qRight;

        if (2 * sumDiff + 9 * qDiff == 0) {
            return false; // Bob wins
        } else {
            return true; // Alice wins
        }
    }
}
```
### Algorithm
1. First, make a single pass through the string to compute the sum of existing digits and the count of `?` characters for the left and right halves. Let them be `sumLeft`, `sumRight`, `qLeft`, and `qRight`.
2. Calculate the initial difference in sums: `sumDiff = sumLeft - sumRight`.
3. Calculate the difference in the number of `?`s: `qDiff = qLeft - qRight`.
4. The total number of turns is `qLeft + qRight`. If this number is odd, Alice gets one more turn than Bob, including the very last turn. With the last move, she can always ensure the sums are not equal (out of 10 possible digits, at most one can make the sums equal). Therefore, if `qLeft + qRight` is odd, Alice wins.
5. If `qLeft + qRight` is even, both players have an equal number of moves. The game's outcome depends on whether Bob can perfectly balance the contributions from the `?`s to offset the initial `sumDiff`.
6. It can be shown through analysis of optimal strategies that the total change in the sum difference contributed by filling all `?`s will be exactly `9 * (qLeft - qRight) / 2` if Alice tries to increase `sumLeft` and Bob tries to decrease it (or vice-versa). 
7. Bob wins if and only if the initial difference can be perfectly canceled out by the changes from filling `?`s. The condition for Bob to win is: `sumDiff + 9 * qDiff / 2 = 0`.
8. If this condition is met, Bob wins (return `false`). Otherwise, Alice wins (return `true`).

# Solutions
### Java

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

```

### CPP

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

### Python

```python
class Solution:
    def sumGame(self, num: str) -> bool: n = len(num) cnt1 = num[: n // 2]. count("?") cnt2 = num[n // 2:]. count("?") s1 = sum(int(x) for x in num[: n // 2] if x != "?") s2 = sum(int(x) for x in num[n // 2:] if x != "?") return (cnt1 + cnt2) % 2 == 1 or s1 - s2 != 9 * (cnt2 - cnt1) // 2

```