Alice and Bob take turns playing a game, with Alice&nbsp;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:


	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&nbsp;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&nbsp;to win, the sums must not be equal.


	For example, if the game ended with num = "243801", then Bob&nbsp;wins because 2+4+3 = 8+0+1. If the game ended with num = "243803", then Alice&nbsp;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.

&nbsp;
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.


&nbsp;
Constraints:


	2 &lt;= num.length &lt;= 105
	num.length is even.
	num consists of only digits and '?'.


class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        q_cnt_1 = s1 = 0
        for i in range(n//2): # get digit sum and question mark count for the first half of `num`
            if num[i] == '?':
                q_cnt_1 += 1
            else:
                s1 += int(num[i])
        q_cnt_2 = s2 = 0
        for i in range(n//2, n): # get digit sum and question mark count for the second half of `num`
            if num[i] == '?':
                q_cnt_2 += 1
            else:
                s2 += int(num[i])
        s_diff = s1 - s2 # calculate sum difference and question mark difference
        q_diff = q_cnt_2 - q_cnt_1
        return not (q_diff % 2 == 0 and q_diff // 2 * 9 == s_diff) # When Bob can't win, Alice wins
class Solution {
    public boolean sumGame(String num) {
        int q = 0, d = 0, n = num.length();
        for (int i = 0; i < n; i++){
            if (num.charAt(i) == '?'){
                q += 2* i < n? 1 : -1;
            }else{
                d += (2 * i < n? 1 : -1) * (num.charAt(i) - '0');
            }
        }
        return (q & 1) > 0 || q * 9 + 2 * d != 0;
    }
}
class Solution {
public:
    bool sumGame(string num) {
        const int N = num.length();
        
        int lDigitSum = 0;
        int lQCount = 0;
        int rDigitSum = 0;
        int rQCount = 0;
        
        for(int i = 0; i < N; ++i){
            if(isdigit(num[i])){
                if(i < N / 2){
                    lDigitSum += (num[i] - '0');
                }else{
                    rDigitSum += (num[i] - '0');
                }
            }else{
                if(i < N / 2){
                    ++lQCount;
                }else{
                    ++rQCount;
                }
            }
        }
        
        // Case 0: Only digits (without '?')
        if((lQCount + rQCount) == 0){
            return (lDigitSum != rDigitSum);
        }
        
        // Case 1: Odd number of '?'
        if((lQCount + rQCount) % 2 == 1){
            return true;
        }
        
        // Case 2: Even number of '?'
        int minQCount = min(lQCount, rQCount);
        lQCount -= minQCount;
        rQCount -= minQCount;
        return (lDigitSum + 9 * lQCount / 2 != rDigitSum + 9 * rQCount / 2);
    }
};
/**
 * @param {string} num
 * @return {boolean}
 */
var sumGame = function(num) {
    
    function getInfo(s) {
        var sum = 0;
        var ques = 0;
        for(let c of s.split(''))
            if (c !== '?') sum += c - 0;
            else ques++;
        return [sum, ques];
    }
    
    function check(sum1, sum2, q1, q2, q) {
        return sum1 + 9* Math.min(q/2, q1) > sum2 + 9 * Math.min(q/2, q2);
    }
    
    
    var q = getInfo(num)[1];
    var [sum1, q1] = getInfo(num.substring(0, Math.floor(num.length/2)));
    var [sum2, q2] = getInfo(num.substring(Math.floor(num.length/2), num.length));
    if (sum1 < sum2) { 
        [sum1, sum2] = [sum2, sum1];
        [q1, q2] = [q2, q1];
    }
    
    return check(sum1, sum2, q1, q2, q) || check(sum2, sum1, q2, q1, q);
};
Sum Game