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 andfalse if Bob will win.

Examples

Example 1

1
2
3
4

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

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

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 <= 10^5
  • num.length is even.
  • num consists of only digits and '?'.

Solution

Method 1 – Game Theory and Greedy

Intuition

Count the sum and number of ‘?’ in both halves. Each ‘?’ can be replaced by any digit, so the player can maximize or minimize the sum in their half. If the difference in possible maximums is not zero, Alice can always force a win.

Approach

  1. Split the string into two halves.
  2. For each half, count the sum of digits and the number of ‘?’.
  3. Let diff = (sum_left - sum_right), and qdiff = (q_left - q_right).
  4. Each ‘?’ can be replaced by a digit 0-9, and the player can maximize their half by choosing 9 or minimize by choosing 0.
  5. If 2 * diff != -qdiff * 9, Bob can never make the sums equal, so Alice wins. Otherwise, Bob wins.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool sumGame(string num) {
        int n = num.size(), s1 = 0, s2 = 0, q1 = 0, q2 = 0;
        for (int i = 0; i < n/2; ++i) {
            if (num[i] == '?') q1++;
            else s1 += num[i] - '0';
        }
        for (int i = n/2; i < n; ++i) {
            if (num[i] == '?') q2++;
            else s2 += num[i] - '0';
        }
        return 2 * (s1 - s2) != 9 * (q2 - q1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func sumGame(num string) bool {
    n := len(num)
    s1, s2, q1, q2 := 0, 0, 0, 0
    for i := 0; i < n/2; i++ {
        if num[i] == '?' {
            q1++
        } else {
            s1 += int(num[i] - '0')
        }
    }
    for i := n/2; i < n; i++ {
        if num[i] == '?' {
            q2++
        } else {
            s2 += int(num[i] - '0')
        }
    }
    return 2*(s1-s2) != 9*(q2-q1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean sumGame(String num) {
        int n = num.length(), s1 = 0, s2 = 0, q1 = 0, q2 = 0;
        for (int i = 0; i < n/2; i++) {
            if (num.charAt(i) == '?') q1++;
            else s1 += num.charAt(i) - '0';
        }
        for (int i = n/2; i < n; i++) {
            if (num.charAt(i) == '?') q2++;
            else s2 += num.charAt(i) - '0';
        }
        return 2 * (s1 - s2) != 9 * (q2 - q1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun sumGame(num: String): Boolean {
        val n = num.length
        var s1 = 0; var s2 = 0; var q1 = 0; var q2 = 0
        for (i in 0 until n/2) {
            if (num[i] == '?') q1++ else s1 += num[i] - '0'
        }
        for (i in n/2 until n) {
            if (num[i] == '?') q2++ else s2 += num[i] - '0'
        }
        return 2 * (s1 - s2) != 9 * (q2 - q1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        s1 = s2 = q1 = q2 = 0
        for i in range(n//2):
            if num[i] == '?':
                q1 += 1
            else:
                s1 += int(num[i])
        for i in range(n//2, n):
            if num[i] == '?':
                q2 += 1
            else:
                s2 += int(num[i])
        return 2 * (s1 - s2) != 9 * (q2 - q1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn sum_game(num: String) -> bool {
        let n = num.len();
        let (mut s1, mut s2, mut q1, mut q2) = (0, 0, 0, 0);
        let bytes = num.as_bytes();
        for i in 0..n/2 {
            if bytes[i] == b'?' { q1 += 1; } else { s1 += (bytes[i] - b'0') as i32; }
        }
        for i in n/2..n {
            if bytes[i] == b'?' { q2 += 1; } else { s2 += (bytes[i] - b'0') as i32; }
        }
        2 * (s1 - s2) != 9 * (q2 - q1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    sumGame(num: string): boolean {
        const n = num.length;
        let s1 = 0, s2 = 0, q1 = 0, q2 = 0;
        for (let i = 0; i < n/2; i++) {
            if (num[i] === '?') q1++;
            else s1 += +num[i];
        }
        for (let i = n/2; i < n; i++) {
            if (num[i] === '?') q2++;
            else s2 += +num[i];
        }
        return 2 * (s1 - s2) !== 9 * (q2 - q1);
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each character is processed once.
  • 🧺 Space complexity: O(1) — Only a few variables are used.