{x}
blog image

Sum Game

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 '?'.

Solution Explanation for LeetCode 1927: Sum Game

This problem involves a two-player game with strategic decision-making. The goal is to determine whether Alice (the first player) has a winning strategy.

Problem Overview:

Alice and Bob take turns replacing '?' characters in a string num (of even length) with digits 0-9. Bob wins if the sum of digits in the first half of the final string equals the sum of digits in the second half. Alice wins otherwise. We need to determine if Alice can always win, regardless of Bob's moves.

Solution Approach (Case Analysis):

The solution uses a clever case analysis based on the number of '?' characters and the initial difference in sums between the two halves of the string.

  1. Odd Number of '?'s: If there's an odd number of '?'s, Alice can always win. She can simply choose her last move to create an imbalance between the sums of the two halves, regardless of what Bob does before.

  2. Even Number of '?'s: This is the more interesting case. The core idea lies in analyzing the difference between the sums of the two halves (s1 - s2). Let cnt1 and cnt2 be the number of '?'s in the first and second halves, respectively. We're interested in how this difference changes as players make moves.

    • Alice aims to maintain a difference (d = s1 - s2) that cannot be neutralized by Bob. If d is not a multiple of 9 (specifically, not equal to 9 * (cnt2 - cnt1) / 2), Alice wins because any move by Bob can't make the difference 0.

    • If the difference is already 9 * (cnt2 - cnt1) / 2 (a multiple of 9), and there are an even number of ?'s left, then Bob can always win because he can always match Alice's moves to keep the difference 0.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string num. This is because we iterate through the string once to count the '?'s and calculate the initial sums.

  • Space Complexity: O(1). The solution uses a constant amount of extra space to store variables like cnt1, cnt2, s1, and s2.

Code Implementation (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

The code efficiently calculates the necessary counts and sums, and then applies the winning condition logic directly. Other language implementations would follow a similar structure. The key insight is the analysis of the difference in sums and how it relates to the number of remaining '?' characters.