We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum Game

Number: 2039

Difficulty: Medium

Paid? No

Companies: ByteDance, DE Shaw

Problem Description

Two players, Alice and Bob, take turns replacing '?' characters in a given even-length string with digits. Alice goes first, and the game ends when there are no '?' left. Bob wins if the sum of digits in the first half equals the sum of digits in the second half; otherwise, Alice wins. Given that both play optimally, determine the winner.

Key Insights

  • The order of moves does not affect the final outcome; only the initial known digits and the count of '?' characters in each half matter.
  • Each '?' can be thought of as having the potential to contribute a maximum difference of 9, but since moves alternate, each move can only secure half of that impact.
  • If we let countLeft and countRight be the number of '?' in the first and second halves and sumLeft and sumRight be the sum of known digits in the two halves, then Bob can force a draw (win) if and only if 2 * (sumLeft - sumRight) equals 9 * (countRight - countLeft).
  • This is because any difference in the digit sums from known digits can be offset by strategically placing the digits 9 and 0 in the unknown positions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), using only fixed extra space for counting.

Solution

The solution involves iterating over the string's two halves separately. For each half, sum the known digits and count the '?' characters. With these, compute the difference in sums (sumLeft - sumRight) and the difference in counts (countRight - countLeft). The balancing condition is:   2 * (sumLeft - sumRight) == 9 * (countRight - countLeft). If the condition is met, Bob can counteract any move by Alice, so Bob wins and the function returns false. Otherwise, Alice wins and the function returns true.

The key data structures used are simple counters and arithmetic operations. The algorithmic approach is greedy in that players attempt to maximize the difference when it is in their favor, but ultimately the comparison of the expected potential differences decides the outcome.

Code Solutions

# Python solution for the Sum Game

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        # Initialize sums and counts for each half
        left_sum, right_sum = 0, 0
        left_count, right_count = 0, 0
        
        # Process the first half of the string
        for i in range(n // 2):
            if num[i] == '?':
                left_count += 1
            else:
                left_sum += int(num[i])
                
        # Process the second half of the string
        for i in range(n // 2, n):
            if num[i] == '?':
                right_count += 1
            else:
                right_sum += int(num[i])
        
        # Check the balancing condition:
        # Bob wins if 2*(left_sum - right_sum) == 9*(right_count - left_count)
        return not (2 * (left_sum - right_sum) == 9 * (right_count - left_count))

# Example usage:
# sol = Solution()
# print(sol.sumGame("25??"))  # Expected output: True
← Back to All Questions