0889MediumMathStringGreedyGame Theory

Splitting a Tally Fairly

Tracked in this browser only

Trains the technique from

LeetCode 1927Sum Game

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tally reads num, a string of even length made of digits and '?' marks.

Two clerks fill the marks in turn, the first clerk going first. A turn means picking any remaining '?' and writing any digit from 0 to 9 into it. Play ends once no marks remain.

Split the finished tally down the middle into two halves of equal length. The second clerk wins when the digits of the two halves add up to the same amount, and the first clerk wins otherwise. Both play as well as they can.

Return true when the first clerk can force a win.

Examples

Example 1

Input: num = "47?3?8"
Output: false

One mark sits in each half and the known digits leave the left half four behind. With two marks the clerks take one each, and whichever digit the first clerk writes the second cannot always close a gap of four, so the first clerk wins.

Example 2

Input: num = "900??0"
Output: false

The left half totals 9 and both marks sit in the right half. Whatever digit the first clerk writes, the second clerk writes nine minus it, and the halves come out level.

Example 3

Input: num = "??"
Output: false

The second clerk simply copies whatever the first clerk wrote into the other mark.

Constraints

2 <= num.length <= 10^5
num.length is even
num consists of digits and '?' only

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def sum_game(num: str) -> bool:

Java

public boolean sumGame(String num)

The intended approach

Time O(n) for a tally of length n, one pass.Space O(1).

Where a mark sits inside its half never matters, only which half it is in, so the whole position is three numbers: the marks left on the left, the marks left on the right, and how far the known digits already tip the balance. With an odd number of marks the first clerk always wins: they can always leave the position unbalanced on the final move. With an even number, the two clerks split the marks evenly, and the second clerk's power is exactly that every digit the first clerk writes can be answered by the complementary digit on the other side, each such pair moving the balance by nine. So the second clerk holds the tally level precisely when the marks that sit on one side outnumber the other's by twice the gap the known digits leave, measured in nines. Working that out is one pass over the tally, and the first clerk wins in every other case. The odd case is worth a second look, because the equation already covers it: an odd number of marks means the two sides differ by an odd count, nine times an odd count is odd, and twice the balance is even, so the two can never meet. Testing the count's parity first is therefore only there to make the argument plain.

Pythonentry point: sum_game

def sum_game(num):
    n = len(num)
    half = n // 2
    left_marks = 0
    right_marks = 0
    balance = 0
    for i in range(n):
        ch = num[i]
        if ch == "?":
            if i < half:
                left_marks += 1
            else:
                right_marks += 1
        else:
            if i < half:
                balance += ord(ch) - 48
            else:
                balance -= ord(ch) - 48
    marks = left_marks + right_marks
    if marks % 2 == 1:
        return True
    return balance * 2 != 9 * (right_marks - left_marks)

The obvious version

Search the game itself. A position is the marks left on each side plus the running balance, and each turn tries all ten digits on either side, the first clerk keeping any line that ends unbalanced and the second keeping any that ends level. Remembers positions already settled. Explores the play rather than reasoning about it.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_sum_game(num):
    n = len(num)
    half = n // 2
    left_marks = 0
    right_marks = 0
    balance = 0
    for i in range(n):
        ch = num[i]
        if ch == "?":
            if i < half:
                left_marks += 1
            else:
                right_marks += 1
        else:
            if i < half:
                balance += ord(ch) - 48
            else:
                balance -= ord(ch) - 48

    memo = {}

    def first_wins(a, b, diff, turn):
        if a == 0 and b == 0:
            return diff != 0
        key = (a, b, diff, turn)
        if key in memo:
            return memo[key]
        results = []
        for digit in range(10):
            if a > 0:
                results.append(first_wins(a - 1, b, diff + digit, 1 - turn))
            if b > 0:
                results.append(first_wins(a, b - 1, diff - digit, 1 - turn))
        if turn == 0:
            answer = any(results)
        else:
            answer = all(results)
        memo[key] = answer
        return answer

    return first_wins(left_marks, right_marks, balance, 0)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in