Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1927.html

1927. Sum Game

Level

Medium

Description

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

Solution

Calculate the sums of the two halves of num and count the number of '?' characters in the two halves. If it is impossible to make the two halves have equal sums, return true. Otherwise, return true if and only if the difference of sums is not a multiple of 9.

  • class Solution {
    public boolean sumGame(String num) {
        int sum1 = 0, sum2 = 0;
        int remain1 = 0, remain2 = 0;
        int length = num.length();
        int halfLength = length / 2;
        for (int i = 0; i < halfLength; i++) {
            char c = num.charAt(i);
            if (c == '?')
                remain1++;
            else
                sum1 += c - '0';
        }
        for (int i = halfLength; i < length; i++) {
            char c = num.charAt(i);
            if (c == '?')
                remain2++;
            else
                sum2 += c - '0';
        }
        if ((remain1 + remain2) % 2 != 0)
            return true;
        int difference = sum1 - sum2;
        if (difference == 0)
            return remain1 != remain2;
        if (difference > 0 && remain1 >= remain2)
            return true;
        if (difference < 0 && remain1 <= remain2)
            return true;
        if (difference > 0) {
            if (difference < 9)
                return true;
            int maxDifference = (remain2 - remain1) / 2 * 9;
            return maxDifference != difference;
        } else {
            if (difference > -9)
                return true;
            int maxDifference = (remain1 - remain2) / 2 * 9;
            return maxDifference != -difference;
        }
    }
}

  • // OJ: https://leetcode.com/problems/sum-game/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/sum-game/discuss/1328966/JavaC%2B%2BPython-Math-Problem-with-Explanation
class Solution {
public:
    bool sumGame(string s) {
        double ans = 0;
        for (int i = 0, N = s.size(); i < N; ++i) {
            ans += (i < N / 2 ? 1 : -1) * (isdigit(s[i]) ? s[i] - '0' : 4.5);
        }
        return ans != 0;
    }
};

  • # 1927. Sum Game
# https://leetcode.com/problems/sum-game/

class Solution:
    def sumGame(self, nums: str) -> bool:
        n = len(nums)
        half = n // 2
        left_sum = sum(int(c) for c in nums[:half] if c != '?')
        right_sum = sum(int(c) for c in nums[half:] if c != '?')
        left_count = nums[:half].count('?')
        right_count = nums[half:].count('?')
        
        def canAliceWin(left_sum, right_sum, left_count, right_count):
            for i in range(left_count + right_count):
                if i % 2 == 0:
                    if left_count > 0:
                        left_sum += 9
                        left_count -= 1
                    else:
                        right_count -= 1
                else:
                    if right_count > 0:
                        right_sum += 9
                        right_count -= 1
                    else:
                        left_count -= 1
                
            return left_sum > right_sum
        
        return canAliceWin(left_sum, right_sum, left_count, right_count) or canAliceWin(right_sum, left_sum, right_count, left_count)


  • func sumGame(num string) bool {
	n := len(num)
	var cnt1, cnt2, s1, s2 int
	for i := 0; i < n/2; i++ {
		if num[i] == '?' {
			cnt1++
		} else {
			s1 += int(num[i] - '0')
		}
	}
	for i := n / 2; i < n; i++ {
		if num[i] == '?' {
			cnt2++
		} else {
			s2 += int(num[i] - '0')
		}
	}
	return (cnt1+cnt2)%2 == 1 || s1-s2 != (cnt2-cnt1)*9/2
}

  • function sumGame(num: string): boolean {
    const n = num.length;
    let [cnt1, cnt2, s1, s2] = [0, 0, 0, 0];
    for (let i = 0; i < n >> 1; ++i) {
        if (num[i] === '?') {
            ++cnt1;
        } else {
            s1 += num[i].charCodeAt(0) - '0'.charCodeAt(0);
        }
    }
    for (let i = n >> 1; i < n; ++i) {
        if (num[i] === '?') {
            ++cnt2;
        } else {
            s2 += num[i].charCodeAt(0) - '0'.charCodeAt(0);
        }
    }
    return (cnt1 + cnt2) % 2 === 1 || 2 * (s1 - s2) !== 9 * (cnt2 - cnt1);
}

All Problems

All Solutions