Show problems as
Classic problem #1927MediumMathStringGreedyGame Theory

Sum Game

Real-world version: Splitting a Tally Fairly
Tracked in this browser only
Read Sum Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sum_game(num: str) -> bool:
Java
public boolean sumGame(String num)

More on the same topics