1927. Sum Game

Difficulty: Medium

Topics: Staff, Math, String, Greedy, Game Theory, Biweekly Contest 56

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:

Choose an index i wherenum[i] == '?'.
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.

Example 4:

Input: num = "16?5?0592?99852?270?94852?5821?863?303??07956??562578340?36?6281545?8682?867?403158?7311994090401?361520?8?181?8?5?1912??586736786656018??4147039?37??652?13182825323368664640397951??499?747492?7160?618?61888381078443?6215195?526542088744?7???563434803?690?7312353?81190762?7818206558023797??4600?7?2?0726268?3294?84668593?93?4275?86546?046?64703?944?2608860?97887?27387??963980505594569?215?116063214573??89383032613351720611698683?85?6408880?4?1?121921229??7?00??997?7618427?90?691??945??592?5433?563???51?132?70232?11993893??9399628?9884??8238087987892442?968020?052?881788?31956843855?73?3?501796465409700142??90552?594?084687556239093350764??07551???37?46?85?0?11823??087842521862230819711211?98?8?6?343786343474249?901???71?54??397448634???96??75440209987096739?8?09998278??11?203924746???047880944?0?9??312381?29?80667?5?52?7?5850???73?3?80806235573?02?41?605749?46118???1??512????39?51230??411193?0982131497873115360408265208??35?37?2557172941?57?3??9036688122?500?164052?889649284069121?913?5??4?9?983?0?825490?4555594?54429459231994??3?984?934504846?8?1521?196??1653303?916056447?9?36?746665603?581109763292?4?9?55239747???008703538648686868740?3?262?127?667?0027??56465142?1??9524168?1809713?00??5603?818?666?99610?8783004661?6?45?6088079780?9?73929?44807?192158?56?3521396?7???58?9705336?2?6?33?7254236629272543060090974?9?5116??011???2?37?87?860?0?26?984?8168?213757??67623030?744?5827454?387204?04988?1687338660208?6493?0337684854228?94075283086641467477156??26?276376630??1?56579415963?6?98??1562??843?2?3516?99151776?5306?8181234203894?4882459?7765?6815?21??3??489480?8239125848?625?7096?622?6?4?6?265560?0005738?74?1786171851816??38079752007905890?0643124??8?6??40206?262?21?2473282183985?938?3488?51883?12??8??251?7540453?1?97291177797304474?5?33?932491??9139?01?830?785?9041?497236260938474555400?6?0150115?2170987731414??8?8?707188?77982?758154303??66?67?8?140?26?0?420?52?517?273382?5??20182?7?802?235?0042509175051542?01?7027307?0919?1141168760538?925?2795???7018?6?455815710776?160237?362198081905?757844?4626?3591?3?915?9?77389101?1?81779?39728096?0460080?5?87?80010?117??9395??12167450??3475531078328?1?25?27755167?067?5742?518733799?67588366725789?18?48?430?85907156?70?163?0364?01?9292?969?87030825?178?5??16465544?1347?461?297457?393630?277??71?0??6999?8?747??5154642642177694236??702541?036008?2?9773?98?17908498?6180?606634316?02802?130448915?01509?711?713?72321??18404??24???6362427???423??3?0????515347?911221?6?95??8??9?7909?3781544427?28????8??57?81?315?24665077513???6?51?813133?2?132?0886?79686?97612991289?303?5??646??1?63???6186156452?698?90040???08831?930389?204?2?1007?9?2205007474?976?095?92??5??17?06????5948?79?066737?2?788?3103980?582???82?2??2?4042?56766214?204?89?0?66682845161?789649?50?2764247348?036321?2245?27527930?34??79025???809502116?9540666?0561?57?0245??78008409?73?1??4??0236277?360?67094605394349650?78?2?57140960?30119?3??35?03??4486965?619570997001?7628??874079502996746151?62652120?12?44981?89846?80?21112208813233967125?9?5???312?1490983265?53?41?9?78304186230218093?20120603?1707?896555302767?7394?61684?89?3042?4871615019?7?865157?0?1?61632296?9?2509929281?138719249?756?434896??0?335011073?8?14455?02694?5181?5?15?74705689?2423?0??81??4?7512?44?09074123?91060?9193776?769?7?729?908627?56?831342875433?1638????068647?817977041271257?1??46????2179137?69799986?6118?5703?21?5906?363924?7674581?628304971828293?999?84?51?19227639363?4?67?12?2930126488061?060?7?41?69040805533?2?553??0?86?08?5480??7060645692071577493241620355960???579?6?3184095649?138542?774416430006?35120392"
Output: true

Example 5:

Input: num = "1?2"
Output: invalid length, not even

Example 6:

Input: num = "????"
Output: true

Example 7:

Input: num = "0000"
Output: false

Example 8:

Input: num = "9?9?"
Output: true

Example 9:

Input: num = "??99"
Output: false

Example 10:

Input: num = "123456"
Output: false

Example 11:

Input: num = "??????????"
Output: true

Constraints:

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

Hint:

Bob can always make the total sum of both sides equal in mod 9.
Why does the difference between the number of question marks on the left and right side matter?

Solution:

We analyze the game as a zero-sum optimization where each side has a sum we want to make unequal (Alice) or equal (Bob). By treating unknown digits as having an expected value of 4.5 when replaced optimally, we can reduce the game to comparing fixed sums and the number of question marks on each half.

Approach

Compute the difference between the sum of known digits in the left half and the right half.
Count the number of question marks in each half.
On each turn, a player can choose a '?' and set it to any digit 0–9.
Since each '?' can be thought of as contributing an average of 4.5 in optimal play, the game outcome depends on:
- The known sum difference.
- The difference in the count of '?' on left vs right side.
If the total possible adjustment range (9 × number of '?') can make the sums equal, Bob can force equality; otherwise Alice can force inequality.

Let's implement this solution in PHP: 1927. Sum Game

<?php
/**
 * @param String $num
 * @return Boolean
 */
function sumGame(string $num): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param String $c
 * @return Float
 */
function getExpectation(string $c): float
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumGame("5023") .  "\n";           // Output: false
echo sumGame("25??") .  "\n";           // Output: true
echo sumGame("?3295???") .  "\n";       // Output: false
$num = "16?5?0592?99852?270?94852?5821?863?303??07956??562578340?36?6281545?8682?867?403158?7311994090401?361520?8?181?8?5?1912??586736786656018??4147039?37??652?13182825323368664640397951??499?747492?7160?618?61888381078443?6215195?526542088744?7???563434803?690?7312353?81190762?7818206558023797??4600?7?2?0726268?3294?84668593?93?4275?86546?046?64703?944?2608860?97887?27387??963980505594569?215?116063214573??89383032613351720611698683?85?6408880?4?1?121921229??7?00??997?7618427?90?691??945??592?5433?563???51?132?70232?11993893??9399628?9884??8238087987892442?968020?052?881788?31956843855?73?3?501796465409700142??90552?594?084687556239093350764??07551???37?46?85?0?11823??087842521862230819711211?98?8?6?343786343474249?901???71?54??397448634???96??75440209987096739?8?09998278??11?203924746???047880944?0?9??312381?29?80667?5?52?7?5850???73?3?80806235573?02?41?605749?46118???1??512????39?51230??411193?0982131497873115360408265208??35?37?2557172941?57?3??9036688122?500?164052?889649284069121?913?5??4?9?983?0?825490?4555594?54429459231994??3?984?934504846?8?1521?196??1653303?916056447?9?36?746665603?581109763292?4?9?55239747???008703538648686868740?3?262?127?667?0027??56465142?1??9524168?1809713?00??5603?818?666?99610?8783004661?6?45?6088079780?9?73929?44807?192158?56?3521396?7???58?9705336?2?6?33?7254236629272543060090974?9?5116??011???2?37?87?860?0?26?984?8168?213757??67623030?744?5827454?387204?04988?1687338660208?6493?0337684854228?94075283086641467477156??26?276376630??1?56579415963?6?98??1562??843?2?3516?99151776?5306?8181234203894?4882459?7765?6815?21??3??489480?8239125848?625?7096?622?6?4?6?265560?0005738?74?1786171851816??38079752007905890?0643124??8?6??40206?262?21?2473282183985?938?3488?51883?12??8??251?7540453?1?97291177797304474?5?33?932491??9139?01?830?785?9041?497236260938474555400?6?0150115?2170987731414??8?8?707188?77982?758154303??66?67?8?140?26?0?420?52?517?273382?5??20182?7?802?235?0042509175051542?01?7027307?0919?1141168760538?925?2795???7018?6?455815710776?160237?362198081905?757844?4626?3591?3?915?9?77389101?1?81779?39728096?0460080?5?87?80010?117??9395??12167450??3475531078328?1?25?27755167?067?5742?518733799?67588366725789?18?48?430?85907156?70?163?0364?01?9292?969?87030825?178?5??16465544?1347?461?297457?393630?277??71?0??6999?8?747??5154642642177694236??702541?036008?2?9773?98?17908498?6180?606634316?02802?130448915?01509?711?713?72321??18404??24???6362427???423??3?0????515347?911221?6?95??8??9?7909?3781544427?28????8??57?81?315?24665077513???6?51?813133?2?132?0886?79686?97612991289?303?5??646??1?63???6186156452?698?90040???08831?930389?204?2?1007?9?2205007474?976?095?92??5??17?06????5948?79?066737?2?788?3103980?582???82?2??2?4042?56766214?204?89?0?66682845161?789649?50?2764247348?036321?2245?27527930?34??79025???809502116?9540666?0561?57?0245??78008409?73?1??4??0236277?360?67094605394349650?78?2?57140960?30119?3??35?03??4486965?619570997001?7628??874079502996746151?62652120?12?44981?89846?80?21112208813233967125?9?5???312?1490983265?53?41?9?78304186230218093?20120603?1707?896555302767?7394?61684?89?3042?4871615019?7?865157?0?1?61632296?9?2509929281?138719249?756?434896??0?335011073?8?14455?02694?5181?5?15?74705689?2423?0??81??4?7512?44?09074123?91060?9193776?769?7?729?908627?56?831342875433?1638????068647?817977041271257?1??46????2179137?69799986?6118?5703?21?5906?363924?7674581?628304971828293?999?84?51?19227639363?4?67?12?2930126488061?060?7?41?69040805533?2?553??0?86?08?5480??7060645692071577493241620355960???579?6?3184095649?138542?774416430006?35120392";
echo sumGame($num) .  "\n";             // Output: true
echo sumGame("1?2") .  "\n";            // Output: invalid length, not even
echo sumGame("????") .  "\n";           // Output: true
echo sumGame("0000") .  "\n";           // Output: false
echo sumGame("9?9?") .  "\n";           // Output: true
echo sumGame("??99") .  "\n";           // Output: false
echo sumGame("123456") .  "\n";         // Output: false
echo sumGame("??????????") .  "\n";     // Output: true
?>

Explanation:

Let leftSum = sum of known digits in the left half, rightSum = sum of known digits in right half.
Let leftQ = number of '?' in left half, rightQ = number of '?' in right half.
Define diff = leftSum - rightSum.
Each '?' can be replaced by a digit 0–9, which changes the sum difference by some value between -9 and +9 per '?'.
Bob wants to make final diff = 0.
The maximum possible adjustment Bob can make is by using the question marks to close the gap. Since Alice moves first and plays optimally to keep diff ≠ 0, the key insight:
- If leftQ == rightQ, only the known sum diff matters.
- If leftQ != rightQ, the player who moves last on the side with more '?' can decide the outcome.
With optimal play, the game reduces to:
- If diff == 0 and leftQ == rightQ, Bob wins (false).
- Else if the difference between question marks is even and diff can be offset by 9 × (difference in '?') / 2, Bob can force equality.
However, using the expectation method (each '?' → 4.5) simplifies the check:
- Compute expectedDiff = leftSum - rightSum + 4.5 * (leftQ - rightQ).
- If expectedDiff == 0, Bob can force a draw; else Alice can force inequality.

Complexity Analysis

Time: O(n) – single pass through the string.
Space: O(1) – only a few integer variables.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!