Skip to main content
Talentd

Sum Game - Solution & Explanation

MediumMathStringGreedyGame Theory23 min readAsked at: De Shaw
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a numeric string of even length containing digits and '?' characters. The string is split into two equal halves. Players alternately replace '?' with digits 0–9, and Alice wins if the final digit sums of both halves are different. The task is to determine whether Alice can force a win assuming optimal play.

Approach 1: Count '?' and Digits in Each Half (O(n) time, O(1) space)

Traverse the string once and track three values for each half: the digit sum and the number of '?' characters. The difference between the left and right sums determines which side currently has an advantage. Each '?' can change a half's sum by at most 9, so the total potential adjustment depends on how many unknown digits exist on each side. By comparing the current sum difference with the maximum adjustments possible from remaining '?' characters, you can determine if the second player can perfectly balance the sums.

The key observation: if the total number of '?' is odd, Alice automatically wins because she makes the final move and can break equality. If the count is even, check whether the difference in sums can be neutralized by distributing the remaining digits optimally. This turns the problem into simple arithmetic using counts instead of simulating moves.

Approach 2: Game Theory Optimized Detection (O(n) time, O(1) space)

This approach models the game as a deterministic game theory problem. Compute sumLeft, sumRight, and counts of qLeft and qRight. Players try to either maximize or minimize the difference between the halves. Each pair of moves effectively changes the difference by multiples of 9 because a player can place 9 while the opponent may place 0.

If the total number of '?' is odd, Alice has the last move and can always create inequality, guaranteeing a win. If the total is even, evaluate the expression sumLeft - sumRight and compare it with (qRight - qLeft) / 2 * 9. When these values match, Bob can perfectly counter every move and force equal sums. Any other configuration means Alice can push the difference away from zero.

This reasoning avoids simulation and reduces the problem to constant-time arithmetic after a single pass through the string. The logic relies on parity, bounded digit contributions, and optimal adversarial moves—common patterns in greedy and mathematical game problems.

Recommended for interviews: The counting approach is typically expected. It demonstrates that you can convert a turn-based problem into math using digit sums and '?' counts. Explaining the game-theory reasoning behind the balancing formula shows deeper insight and usually impresses interviewers.

Approach 1: Count '?' and Digits in Each Half

This approach involves counting the number of '?' marks and sum of digits for the first half and the second half separately. The difference in the counts determines the control each player has over the final outcome, and hence the winner.

This C solution evaluates the difference in sum after separating the string into two halves. It considers '?' marks as zeros initially, then adjusts potential maximum impacts of unknown digits while comparing sums from each half.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n) since we need to traverse the string once to gather necessary information, and the space complexity is O(1) because we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Game Theory Optimized Detection

Using game theory, examine the outcomes based on current sums and '?'. Depending on whether '?' can be resolved advantageously (or leave it neutral), predict if Alice can always prevent Bob's win.

This strategy considers the equality of options (both sides having equal '?'), simplifying the decision into whether the current sum balance can diverge, helping Alice win.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n) due to the linear examination of the string, with constant space use at O(1).

Try this approach in the editor →

Approach 3: 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.

If the number of '?' is even, Alice will try to make the sums of the two halves different by placing 9 in the half with the larger current sum and 0 in the half with the smaller current sum. Bob, on the other hand, will try to make the sums equal by placing a digit in the other half that matches the digit Alice placed.

As a result, all remaining even-numbered '?' will be concentrated in one half. Suppose the current difference between the sums of the two halves is d.

Let's consider the case where there are two remaining '?' and the difference is x:

  • If x \lt 9, Alice will definitely win because she can replace one of the '?' with 9, making the sums of the two halves different.
  • If x \gt 9, Alice will definitely win because she can replace one of the '?' with 0, making the sums of the two halves different.
  • If x = 9, Bob will definitely win. Suppose Alice replaces a digit with a, then Bob can replace the other '?' with 9 - a, making the sums of the two halves equal.

Therefore, if the difference between the sums of the two halves is d = \frac{9 times cnt}{2}, where cnt is the number of remaining '?', Bob will definitely win; otherwise, Alice will definitely win.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Count '?' and Digits in Each Half

The time complexity is O(n) since we need to traverse the string once to gather necessary information, and the space complexity is O(1) because we are using a constant amount of extra space.

Game Theory Optimized Detection

The time complexity is O(n) due to the linear examination of the string, with constant space use at O(1).

Case Analysis—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Count '?' and Digit SumsO(n)O(1)General solution; simple single-pass counting and arithmetic reasoning
Game Theory Optimized DetectionO(n)O(1)When analyzing optimal play and parity logic in interview game problems

Video Solution

LEETCODE BIWEEKLY CONTEST 56 | PROBLEM 1925 , 1926, 1927 | LEETCODE | CODE EXPLAIENR • code Explainer • 2,417 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Sum Game easy or hard?
Sum Game is rated Medium on LeetCode. The implementation is straightforward once you derive the mathematical condition, but recognizing the game-theory insight about '?' parity and maximum digit adjustments is the challenging part.
How to solve Sum Game in O(n)?
Iterate through the string and compute sumLeft, sumRight, qLeft, and qRight. If the total number of '?' is odd, Alice wins. Otherwise check whether sumLeft - sumRight equals (qRight - qLeft) / 2 * 9. Equality means Bob can force balanced sums; otherwise Alice has a winning strategy.
What is the best approach for Sum Game?
The optimal approach counts digit sums and '?' characters in both halves of the string. After a single O(n) pass, use arithmetic to check whether Bob can balance the sums. If the total number of '?' is odd, Alice wins immediately; otherwise compare the sum difference with the maximum adjustment possible using remaining digits.
Is Sum Game asked at Google/Amazon/Meta?
Sum Game represents a classic interview pattern combining greedy reasoning and game theory. Variants of digit-balancing and optimal-play problems appear in interviews at large tech companies including Google, Amazon, and Meta when evaluating algorithmic reasoning.
What data structure is used in Sum Game?
No complex data structure is required. The solution relies on simple counters for digit sums and counts of '?' characters while iterating through the string. The core reasoning comes from math and game theory rather than data structures.
What is the time complexity of Sum Game?
The optimal solution runs in O(n) time because it scans the string once to compute digit sums and counts of '?'. Space complexity is O(1) since only a few counters are stored regardless of input size.
Sum Game Python or Java solution approach?
Both Python and Java implementations follow the same logic: compute sums and '?' counts for each half, then apply the balancing condition derived from game theory. The code typically fits within 15–20 lines and runs in O(n) time with constant space.

Ready to solve this problem?

Practice Sum Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer