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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum Game

Difficulty: Medium

Problem Description

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 replace a '?' with any digit between '0' and '9'. The game ends when there are no more '?' characters. 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. Assuming both play optimally, return true if Alice will win and false if Bob will win.

Key Insights

  • The game involves manipulating '?' characters to achieve different sums for the two halves.
  • Alice aims to create a situation where the two sums cannot be made equal, while Bob will try to ensure they can be.
  • The number of '?' characters and their distribution between the two halves is crucial to determining the outcome.
  • The sums of the fixed digits in both halves should be compared to the potential contributions from the '?' characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string num. We traverse the string to calculate sums and counts of '?' characters. Space Complexity: O(1), since we use a fixed amount of space for variables regardless of the input size.

Solution

To solve the problem, we will:

  1. Split the string into two halves.
  2. Calculate the sum of digits in both halves, ignoring '?' characters.
  3. Count the number of '?' characters in each half.
  4. Determine the maximum possible difference between the sums based on the '?' counts and the contributions they can make.
  5. Based on the calculated sum differences and the ability to manipulate '?' characters, conclude whether Alice can guarantee a win.

Code Solutions

def sumGame(num: str) -> bool:
    n = len(num)
    half = n // 2
    
    sum_a = sum(int(num[i]) for i in range(half) if num[i] != '?')
    sum_b = sum(int(num[i]) for i in range(half, n) if num[i] != '?')
    
    question_marks_a = num[:half].count('?')
    question_marks_b = num[half:].count('?')
    
    difference = (sum_a - sum_b)
    
    # Maximum contribution of '?' in both halves
    max_contribution_a = question_marks_a * 9
    max_contribution_b = question_marks_b * 9
    
    # Check if Alice can always win
    if difference < 0:  # Bob is ahead
        return not (difference + max_contribution_a >= 0 and -difference + max_contribution_b >= 0)
    elif difference > 0:  # Alice is ahead
        return not (difference - max_contribution_b <= 0 and -difference - max_contribution_a <= 0)
    else:  # They are equal
        return not (max_contribution_a + max_contribution_b >= 0)
← Back to All Questions