#1927

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Sum Game

Determine if Alice can force a win in the Sum Game by strategically replacing '?' using a greedy and invariant approach.

math string greedy game theory

Problem Statement

Alice and Bob play a game starting with Alice. You are given a string num of even length containing digits and '?' characters. On each turn, the current player replaces one '?' with a digit from 0 to 9.

The game ends when no '?' remain. Alice wins if the sum of the first half differs from the sum of the second half. Otherwise, Bob wins. Determine if Alice can guarantee a win assuming both play optimally.

Examples

Example 1

Input: num = "5023"

Output: false

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

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

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 Approach

Calculate current sums and unknowns

Split num into two halves. Count sum of digits and number of '?' in each half. This provides the initial state for invariant validation and greedy analysis.

Apply greedy replacement strategy

Alice should always replace a '?' to maximize the sum difference in her favor, while Bob aims to balance sums. Consider the effect of each replacement on the sum modulo 9 to anticipate final outcomes.

Evaluate invariant to predict winner

After all replacements, use the formula comparing weighted sums and remaining '?' contributions. If Alice can force the difference to be nonzero, she wins. Otherwise, Bob can always counter to equalize sums.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed once to compute sums and count '?'. Space complexity is O(1) beyond input storage as only counters are used.

What Interviewers Usually Probe

Looking for correct sum tracking and handling of '?'
Expect insight into greedy strategy and modular reasoning
Checking ability to predict outcome before simulating all moves

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider distribution of '?' between halves
Assuming Alice can always pick optimal digits without considering Bob's counters
Neglecting modulo arithmetic leading to wrong winner prediction

Follow-up variants

Sum Game with odd length strings requiring extra rules
Allow '?' to be replaced with digits outside 0-9 range
Multiple players alternating instead of just Alice and Bob

FAQ

What is the main strategy to solve Sum Game?

Use a greedy approach to replace '?' and maintain invariant checks on the sums of each half to determine if Alice can win.

Why do we consider modulo 9 in Sum Game?

Modulo 9 captures the effect of digit replacements on the sum difference efficiently and predicts if Bob can always balance the halves.

How do '?' positions affect the game outcome?

The number and location of '?' in each half determine if Alice can force a sum difference or if Bob can always counter to equalize sums.

Can Alice always win if she starts first?

No, Alice can only guarantee a win if the combination of '?' distribution and existing sums allows her greedy moves to unbalance the halves.

What pattern does Sum Game exemplify?

It demonstrates the greedy choice plus invariant validation pattern, where optimal local choices and sum invariants predict the winner.

terminal

Solution

Solution 1: Case Analysis

If the number of `'?'` is odd, Alice will definitely win because she can choose to replace the last `'?'` with any digit, making the sum of the first half different from the sum of the second half.

1

2

3

4

5

6

7

8

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

Continue Practicing

#2038 remove colored pieces if both neighbors are the same color #1903 largest odd number in string #2029 stone game ix