1927. Sum Game

Problem Overview

Alice wants the two halves different; Bob wants them equal.

Intuition

Alice wants the two halves different; Bob wants them equal. Each question mark can become any digit 0..9. Under optimal play that choice is worth 4.5, the midpoint of the range. Add 4.5 (or the known digit) on the left half and subtract it on the right. If the signed total is not zero, Alice can keep the halves apart. If it is zero, Bob can always cancel.

Algorithm

1Let n be the even length of num. Initialise ans = 0.
2For i in [0, n/2): add 4.5 if num[i] is '?', else add the digit.
3For i in [n/2, n): subtract the same value.
4Return whether ans is not 0.

Example Walkthrough

Input: num = "25??"

1.Left half "25" contributes 2 + 5 = 7.
2.Right half "??" contributes 4.5 + 4.5 = 9.
3.7 - 9 = -2, not zero, so Alice wins.

Output: true

Common Pitfalls

•Compare with 0.0 after the signed sum. Do not early-return on the first question mark.
•A known digit is itself, not 4.5. Only '?' uses the midpoint.
•The two halves are equal length. Split at n/2, not at the first '?'.
•This is not a simulation of turns. The 4.5 test already encodes optimal play.

1927.cs

// Approach: Alice wins iff the two halves cannot be forced equal. Treat each
// '?' as 4.5 (the midpoint of 0..9). Add that value on the left half and
// subtract it on the right. A non-zero total means Alice can keep the sums
// different; zero means Bob can always cancel.
// Complexity: O(n) time and O(1) extra space.
public class Solution
{
    public bool SumGame(string num)
    {
        int n = num.Length;
        double ans = 0.0;

        for (int i = 0; i < n / 2; ++i)
            ans += GetExpectation(num[i]);

        for (int i = n / 2; i < n; ++i)
            ans -= GetExpectation(num[i]);

        return ans != 0.0;
    }

    private double GetExpectation(char c)
    {
        return c == '?' ? 4.5 : c - '0';
    }
}

Was this solution helpful?