Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Sum Game solution and explanation

MediumGame TheoryGreedyMathString8 min read63.5% acceptanceUpdated 9 Apr 2026
Asked atD. E. Shaw
Practise Sum Game
19:31
LEETCODE BIWEEKLY CONTEST 56 | PROBLEM 1925 , 1926, 1927 | LEETCODE | CODE EXPLAIENRcode Explainer · 19:31 · 2K viewsWatch on YouTube
5 more videos on this problem
  1. LEETCODE BIWEEKLY CONTEST 56 | PROBLEM 1925 , 1926, 1927 | LEETCODE | CODE EXPLAIENRcode Explainer · 19:31 · 2K views
  2. LeetCode 1927. Sum GameHappy Coding · 25:39 · 2K views
  3. LeetCode 1927. Sum GameSakura Programming · 5:28 · 579 views
  4. 1927. Sum Game (Leetcode Medium)Programming Live with Larry · 44:36 · 565 views
  5. LeetCode 1927 - Sum Game - PythonAlpha-Code · 24:13 · 99 views
  6. LeetCode 1927: Sum GameAlitaCode · 29:26 · 12 views

The problem

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.

def sumGame(num):
    n = len(num)
    half = n // 2
    leftSum, rightSum, leftQ, rightQ = 0, 0, 0, 0
    for i in range(half):
        if num[i] == '?':
            leftQ += 1
        else:
            leftSum += int(num[i])
    for i in range(half, n):
        if num[i] == '?':
            rightQ += 1
        else:
            rightSum += int(num[i])
    diffQ = leftQ - rightQ
    diffSum = leftSum - rightSum
    return (diffQ % 2 != 0) or (diffSum * 9 != diffQ / 2)

print(sumGame('25??'))  # true
print(sumGame('?3295???'))  # false
public class SumGame {
    public static boolean sumGame(String num) {
        int n = num.length();
        int half = n / 2;
        int leftSum = 0, rightSum = 0, leftQ = 0, rightQ = 0;
        for (int i = 0; i < half; i++) {
            if (num.charAt(i) == '?') leftQ++;
            else leftSum += num.charAt(i) - '0';
        }
        for (int i = half; i < n; i++) {
            if (num.charAt(i) == '?') rightQ++;
            else rightSum += num.charAt(i) - '0';
        }
        int diffQ = leftQ - rightQ;
        int diffSum = leftSum - rightSum;
        return diffQ % 2 != 0 || diffSum != diffQ / 2 * 9;
    }

    public static void main(String[] args) {
        System.out.println(sumGame("25??"));  // true
        System.out.println(sumGame("?3295???"));  // false
    }
}
#include <iostream>
using namespace std;

bool sumGame(string num) {
    int n = num.length();
    int half = n / 2;
    int leftSum = 0, rightSum = 0, leftQ = 0, rightQ = 0;
    for (int i = 0; i < half; ++i) {
        if (num[i] == '?') leftQ++;
        else leftSum += num[i] - '0';
    }
    for (int i = half; i < n; ++i) {
        if (num[i] == '?') rightQ++;
        else rightSum += num[i] - '0';
    }
    int diffQ = leftQ - rightQ;
    int diffSum = leftSum - rightSum;
    return diffQ % 2 != 0 || diffSum != diffQ / 2 * 9;
}

int main() {
    cout << sumGame("25??") << endl;  // true
    cout << sumGame("?3295???") << endl;  // false
    return 0;
}
function sumGame(num) {
    const n = num.length;
    const half = n / 2;
    let leftSum = 0, rightSum = 0, leftQ = 0, rightQ = 0;
    for (let i = 0; i < half; i++) {
        if (num[i] === '?') leftQ++;
        else leftSum += Number(num[i]);
    }
    for (let i = half; i < n; i++) {
        if (num[i] === '?') rightQ++;
        else rightSum += Number(num[i]);
    }
    const diffQ = leftQ - rightQ;
    const diffSum = leftSum - rightSum;
    return diffQ % 2 !== 0 || diffSum !== 9 * (diffQ / 2);
}

console.log(sumGame('25??'));  // true
console.log(sumGame('?3295???'));  // false;
#include <stdio.h>
#include <stdbool.h>

bool sumGame(char *num) {
    int n = 0;
    while (num[n]) n++;
    int half = n / 2, leftSum = 0, rightSum = 0, leftQ = 0, rightQ = 0;
    for (int i = 0; i < half; i++) {
        if (num[i] == '?') leftQ++;
        else leftSum += num[i] - '0';
    }
    for (int i = half; i < n; i++) {
        if (num[i] == '?') rightQ++;
        else rightSum += num[i] - '0';
    }
    int diffQ = leftQ - rightQ, diffSum = leftSum - rightSum;
    return (diffQ % 2 != 0) || (diffSum * (9 * diffQ / 2) != 0);
}

int main() {
    printf("%d\n", sumGame("25??"));  // true
    printf("%d\n", sumGame("?3295???"));  // false
    return 0;
}
using System;

public class SumGame {
    public static bool sumGame(string num) {
        int n = num.Length;
        int half = n / 2;
        int leftSum = 0, rightSum = 0, leftQ = 0, rightQ = 0;
        for (int i = 0; i < half; i++) {
            if (num[i] == '?') leftQ++;
            else leftSum += num[i] - '0';
        }
        for (int i = half; i < n; i++) {
            if (num[i] == '?') rightQ++;
            else rightSum += num[i] - '0';
        }
        int diffQ = leftQ - rightQ;
        int diffSum = leftSum - rightSum;
        return diffQ % 2 != 0 || diffSum != diffQ / 2 * 9;
    }

    public static void Main(string[] args) {
        Console.WriteLine(sumGame("25??"));  // true
        Console.WriteLine(sumGame("?3295???"));  // false
    }
}

The Python implementation traverses the string, simultaneously collecting '?' counts and digit sums for both halves, then calculating discrepancies to decide the winner.

Complexity

Time complexity remains O(n) for the single pass and space complexity is O(1) because no additional data structures are utilized.

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.

def sumGame(num):
    n = len(num)
    left_opts, right_opts, balance = 0, 0, 0
    for i in range(n):
        if num[i] == '?':
            if i < n // 2:
                left_opts += 1
            else:
                right_opts += 1
        else:
            if i < n // 2:
                balance += int(num[i])
            else:
                balance -= int(num[i])
    if left_opts == right_opts:
        return balance != 0
    return (left_opts + right_opts) % 2 != 0

print(sumGame('25??'))  # true
print(sumGame('?3295???'))  # false
public class SumGame {
    public static boolean sumGame(String num) {
        int n = num.length();
        int left_opts = 0, right_opts = 0;
        int balance = 0;
        for (int i = 0; i < n; i++) {
            if (num.charAt(i) == '?') {
                if (i < n / 2) left_opts++;
                else right_opts++;
            } else {
                if (i < n / 2) balance += num.charAt(i) - '0';
                else balance -= num.charAt(i) - '0';
            }
        }
        if (left_opts == right_opts) return (balance != 0);
        return (left_opts + right_opts) % 2 != 0;
    }

    public static void main(String[] args) {
        System.out.println(sumGame("25??"));  // true
        System.out.println(sumGame("?3295???"));  // false
    }
}
#include <iostream>
using namespace std;

bool sumGame(string num) {
    int n = num.size(), left_opts = 0, right_opts = 0;
    int balance = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] == '?') {
            if (i < n / 2) left_opts++;
            else right_opts++;
        } else {
            if (i < n / 2) balance += (num[i] - '0');
            else balance -= (num[i] - '0');
        }
    }
    if (left_opts == right_opts) return (balance != 0);
    return ((left_opts + right_opts) % 2 != 0);
}

int main() {
    cout << sumGame("25??") << endl;  // true
    cout << sumGame("?3295???") << endl;  // false
    return 0;
}
function sumGame(num) {
    const n = num.length;
    let left_opts = 0, right_opts = 0, balance = 0;
    for (let i = 0; i < n; i++) {
        if (num[i] === '?') {
            if (i < n / 2) left_opts++;
            else right_opts++;
        } else {
            if (i < n / 2) balance += Number(num[i]);
            else balance -= Number(num[i]);
        }
    }
    if (left_opts === right_opts) return (balance !== 0);
    return ((left_opts + right_opts) % 2 !== 0);
}

console.log(sumGame('25??'));  // true
console.log(sumGame('?3295???'));  // false;
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool sumGame(char *num) {
    int n = strlen(num), left_opts = 0, right_opts = 0;
    int balance = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] == '?') {
            if (i < n / 2) left_opts++;
            else right_opts++;
        } else {
            if (i < n / 2) balance += (num[i] - '0');
            else balance -= (num[i] - '0');
        }
    }
    if (left_opts == right_opts) return (balance != 0);
    return ((left_opts + right_opts) % 2 != 0);
}

int main() {
    printf("%d\n", sumGame("25??"));  // true
    printf("%d\n", sumGame("?3295???"));  // false
    return 0;
}
using System;

public class SumGame {
    public static bool SumGame(string num) {
        int n = num.Length;
        int left_opts = 0, right_opts = 0, balance = 0;
        for (int i = 0; i < n; i++) {
            if (num[i] == '?') {
                if (i < n / 2) left_opts++;
                else right_opts++;
            } else {
                if (i < n / 2) balance += num[i] - '0';
                else balance -= num[i] - '0';
            }
        }
        if (left_opts == right_opts) return (balance != 0);
        return ((left_opts + right_opts) % 2 != 0);
    }

    public static void Main(string[] args) {
        Console.WriteLine(SumGame("25??"));  // true
        Console.WriteLine(SumGame("?3295???"));  // false
    }
}

Utilizing game theory insights in Python, this solution maps out '?'-induced impacts, balancing initial sum positions to predict winners.

Complexity

Linear operations assure O(n) time complexity with O(1) spatial efficiency.

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).

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);
}
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
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Count '?' and Digits in Each Half

Time complexity remains O(n) for the single pass and space complexity is O(1) because no additional data structures are utilized.

Game Theory Optimized Detection

Linear operations assure O(n) time complexity with O(1) spatial efficiency.

Case Analysis–

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

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.

Comments

Now write it yourselfClose this page and solve Sum Game in the editor, without looking.
Practise Sum Game