LeetCode 1927 - Sum Game

LeetCode Problem 1927

Difficulty: 🟡 Medium
Topics: Math, String, Greedy, Game Theory

Solution

Problem Understanding

The problem describes a two player game played on a numeric string of even length. The string contains digits and possibly some '?' characters. Alice and Bob alternate turns replacing one '?' with a digit from '0' to '9'. Alice moves first.

At the end of the game, every '?' has been replaced. The string is divided into two equal halves. Bob wins only if the sum of the digits in the left half equals the sum of the digits in the right half. Alice wins if the sums are different.

The task is to determine whether Alice wins assuming both players play optimally.

The important observation is that the actual final digits are not arbitrary. Since both players are making choices strategically, the game becomes a question of whether Alice can force the two halves to end with different sums, or whether Bob can always neutralize Alice’s moves and force equality.

The input size can be as large as 10^5, which immediately rules out any exponential simulation of all possible game states. Even a polynomial algorithm with large constants would be risky, so the intended solution must analyze the game mathematically instead of explicitly simulating turns.

Several edge cases are important:

• The string may already contain no '?' characters.
• One half may contain many more unknowns than the other.
• The current digit sums may already differ significantly.
• The total number of '?' characters is always even because the string length is even and both players alternate until all are filled.
• A naive implementation may incorrectly assume players independently maximize or minimize sums without considering alternating turns.

The key challenge is understanding how optimal play affects the balance between the two halves.

Approaches

Brute Force Approach

A brute force solution would recursively simulate every possible move for both players.

At each turn:

1. Pick any remaining '?'.
2. Try every digit from 0 to 9.
3. Recursively evaluate the resulting game state.

Since both players play optimally, the recursion becomes a minimax game tree:

• Alice tries to force an unequal final sum.
• Bob tries to force equality.

This approach is correct because it explores every possible legal move sequence and applies optimal play rules. However, it is completely impractical.

If there are k question marks, then each move has up to 10k possibilities initially, then 10(k-1), and so on. The total state space grows exponentially.

With k potentially near 10^5, brute force is impossible.

Optimal Greedy and Mathematical Observation

The crucial insight is that the exact move order does not matter as much as:

• The current difference between left and right sums.
• How many '?' characters remain in each half.

Let:

• leftSum = known digit sum in left half
• rightSum = known digit sum in right half
• leftQ = number of '?' in left half
• rightQ = number of '?' in right half

Bob wants the final sums equal.

Each pair of future moves can effectively contribute at most 9 difference because one player can place 9 while the other can place 0.

A very elegant observation emerges:

• If the total adjustment possible from the extra '?' characters exactly compensates for the current sum difference, Bob wins.
• Otherwise, Alice wins.

The final condition becomes:

2 * (leftSum - rightSum) == 9 * (rightQ - leftQ)

If this equality holds, Bob can force equality, so Alice loses.

Otherwise, Alice can force inequality, so Alice wins.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Simulates every game state recursively
Optimal	O(n)	O(1)	Uses mathematical game analysis

Algorithm Walkthrough

1. Compute the length of the string and identify the midpoint.

Since the string length is always even, the midpoint cleanly separates the two halves. 2. Traverse the left half.

For each character:

• If it is '?', increment leftQ.
• Otherwise, add its digit value to leftSum.

This gathers all information relevant to the left side. 3. Traverse the right half.

Similarly:

• Count question marks into rightQ.
• Add known digits into rightSum.

4. Compute the current sum difference.

diff = leftSum - rightSum

A positive value means the left side currently leads. 5. Analyze how remaining '?' positions can affect the game.

Every unmatched pair of question marks contributes potential adjustment of 9.

For example:

• Alice can place 9
• Bob can respond with 0

or vice versa. 6. Apply the winning condition.

Bob can force equality only when:

2 * diff == 9 * (rightQ - leftQ)

If this condition holds, return False because Bob wins.

Otherwise, return True because Alice wins.

Why it works

The game reduces to balancing total achievable score adjustments between the two halves.

Question marks that appear symmetrically across both halves cancel each other because Bob can mirror Alice’s moves. Only the imbalance in question mark counts matters.

Each unmatched question mark pair contributes an effective difference capacity of 9. If the current digit difference exactly matches this compensating capacity, Bob can force equality. Otherwise, Alice can always preserve a nonzero difference.

This invariant completely characterizes the game outcome.

Python Solution

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        half = n // 2

        left_sum = 0
        right_sum = 0
        left_q = 0
        right_q = 0

        for i in range(half):
            if num[i] == '?':
                left_q += 1
            else:
                left_sum += int(num[i])

        for i in range(half, n):
            if num[i] == '?':
                right_q += 1
            else:
                right_sum += int(num[i])

        diff = left_sum - right_sum

        return 2 * diff != 9 * (right_q - left_q)

The implementation directly follows the mathematical derivation.

The first half of the code gathers statistics for the left side:

• Sum of known digits
• Count of unknown positions

The second loop performs the same work for the right side.

After computing the current sum difference, the final line checks the key equilibrium condition. If equality holds, Bob can force the final sums to match, so the function returns False. Otherwise, Alice can force inequality, so the function returns True.

The implementation uses only a few integer variables and scans the string once, making it highly efficient for large inputs.

Go Solution

func sumGame(num string) bool {
	n := len(num)
	half := n / 2

	leftSum := 0
	rightSum := 0
	leftQ := 0
	rightQ := 0

	for i := 0; i < half; i++ {
		if num[i] == '?' {
			leftQ++
		} else {
			leftSum += int(num[i] - '0')
		}
	}

	for i := half; i < n; i++ {
		if num[i] == '?' {
			rightQ++
		} else {
			rightSum += int(num[i] - '0')
		}
	}

	diff := leftSum - rightSum

	return 2*diff != 9*(rightQ-leftQ)
}

The Go implementation mirrors the Python solution almost exactly.

One Go specific detail is converting digit characters into integers using:

int(num[i] - '0')

Since all arithmetic values remain well within standard integer ranges, there is no overflow concern.

The solution uses constant extra space because only a few counters and sums are stored.

Worked Examples

Example 1

Input:

"5023"

Split into halves:

Half	Content
Left	"50"
Right	"23"

Processing:

Variable	Value
leftSum	5
rightSum	5
leftQ	0
rightQ	0

Compute:

2 * (5 - 5) = 0
9 * (0 - 0) = 0

Condition holds:

0 == 0

Bob wins.

Output:

false

Example 2

Input:

"25??"

Split into halves:

Half	Content
Left	"25"
Right	"??"

Processing:

Variable	Value
leftSum	7
rightSum	0
leftQ	0
rightQ	2

Compute:

2 * (7 - 0) = 14
9 * (2 - 0) = 18

Condition does not hold:

14 != 18

Alice wins.

Output:

true

Example 3

Input:

"?3295???"

Split into halves:

Half	Content
Left	"?329"
Right	"5???"

Processing:

Variable	Value
leftSum	14
rightSum	5
leftQ	1
rightQ	3

Compute:

2 * (14 - 5) = 18
9 * (3 - 1) = 18

Condition holds:

18 == 18

Bob wins.

Output:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the string
Space	O(1)	Only a few integer variables are used

The algorithm scans the input string exactly once and performs constant time work for each character. No auxiliary data structures proportional to input size are needed.

This efficiency is necessary because the input length may reach 10^5.

Test Cases

sol = Solution()

assert sol.sumGame("5023") == False  # already balanced
assert sol.sumGame("25??") == True  # Alice can force imbalance
assert sol.sumGame("?3295???") == False  # Bob can force equality

assert sol.sumGame("00") == False  # equal sums, no question marks
assert sol.sumGame("01") == True  # unequal sums, no moves possible

assert sol.sumGame("??") == False  # Bob can match Alice's move
assert sol.sumGame("9?") == True  # impossible to balance

assert sol.sumGame("?0") == True  # Alice controls only unknown
assert sol.sumGame("0?") == True  # Alice controls only unknown

assert sol.sumGame("????") == False  # perfectly symmetric unknowns
assert sol.sumGame("1???") == True  # imbalance cannot be corrected

assert sol.sumGame("1234") == True  # fixed unequal sums
assert sol.sumGame("1212") == False  # fixed equal sums

assert sol.sumGame("?5?5") == False  # balanced unknown distribution
assert sol.sumGame("??11") == True  # extra flexibility on left side

assert sol.sumGame("????????") == False  # fully symmetric large unknown case

Test	Why
"5023"	Validates already balanced fixed digits
"25??"	Tests Alice forcing imbalance
"?3295???"	Tests Bob balancing with extra unknowns
"00"	Smallest balanced input
"01"	Smallest unequal fixed input
"??"	Symmetric unknowns
"9?"	Single unknown cannot compensate
"?0"	Left side controlled by Alice
"0?"	Right side controlled by Alice
"????"	Perfect symmetry with all unknowns
"1???"	Large imbalance from known digits
"1234"	Fixed unequal sums
"1212"	Fixed equal sums
"?5?5"	Equalizable mixed configuration
"??11"	Uneven question mark placement
"????????"	Stress test for symmetry

Edge Cases

No Question Marks

An important edge case occurs when the string already contains no '?' characters. In this scenario, the game has no moves at all. The winner is determined entirely by the existing digit sums.

A buggy implementation might incorrectly assume players always make moves or fail to handle zero unknowns properly. The mathematical condition naturally handles this case because both question mark counts become zero.

All Characters Are Question Marks

Consider inputs like "??" or "????".

These cases are tricky because no initial digit information exists. A naive greedy simulation may incorrectly conclude that Alice has an advantage because she moves first.

However, symmetry allows Bob to mirror Alice’s influence and force equality. The formula correctly detects this because the current sum difference is zero and the question mark counts are balanced.

Uneven Distribution of Question Marks

Cases like "25??" are subtle because one half contains significantly more flexibility than the other.

A naive implementation might incorrectly compare only current sums without considering future adjustment potential.

The optimal solution explicitly accounts for how many unknown positions remain in each half. The factor of 9 captures the maximum contribution each unmatched pair can create, ensuring these asymmetric situations are handled correctly.