Sum Game

Medium

DE Shaw

1 view

Topics:

Greedy AlgorithmsArrays

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 where num[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.

Constraints:

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

Sum Game

Medium

DE Shaw

1 view

Topics:

Greedy AlgorithmsArrays

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 where num[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.

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `num`?
Can the input string `num` contain characters other than digits ('0'-'9') and question marks ('?')?
If the number of question marks in the first half and second half are equal, does Bob automatically win, or is there a condition where Alice can still win?
Is the input string `num` guaranteed to have an even length?
By 'Alice and Bob play optimally,' do you mean they are trying to maximize/minimize the difference between the sums of the two halves, respectively, or maximize their own chance of winning regardless of the difference?

Brute Force Solution

Approach

The brute force strategy for the Sum Game means exploring every single possible combination of moves Alice and Bob can make. We essentially simulate the entire game by trying everything. This lets us determine the outcome under perfect play, by exhaustively evaluating the consequences of each decision.

Here's how the algorithm would work step-by-step:

Consider all possible numbers Alice could choose for her move.
For each of Alice's choices, consider all possible numbers Bob could choose for his move in response.
Continue this process for each move each player can make, creating a tree of all possible game scenarios.
Once the game is over in each scenario (all numbers are chosen), determine who wins for that particular game sequence.
After evaluating all possible games, determine the winning strategy by assuming both players play optimally. This means if Alice wants to win, she should always pick the scenario where she wins, and similarly, Bob should pick the scenario where he wins.

Code Implementation

def can_first_player_win(numbers):
    def calculate_sum(nums):
        total_sum = 0
        for num in nums:
            total_sum += num
        return total_sum

    def find_winner(current_numbers, first_players_turn):
        if not current_numbers:
            return calculate_sum(first_half) != calculate_sum(second_half)

        for i in range(len(current_numbers)):
            next_numbers = current_numbers[:i] + current_numbers[i+1:]
            if first_players_turn:
                first_half.append(current_numbers[i])
                winner = find_winner(next_numbers, False)
                first_half.pop()
            else:
                second_half.append(current_numbers[i])
                winner = find_winner(next_numbers, True)
                second_half.pop()
            if winner:
                return True
        return False

    first_half = []
    second_half = []
    all_wins_exist = find_winner(numbers, True)

    return all_wins_exist

def sum_game(number_string):
    numbers = []
    for digit in number_string:
        numbers.append(int(digit))
    
    # If player one can force a win, return True
    return can_first_player_win(numbers)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(4^n) – The provided brute force solution involves exploring all possible game scenarios. Each player has n/2 moves and each move offers 2 choices (a digit from 0-9 to put in a ‘?’). So, if there are n/2 question marks on each side for both Alice and Bob, the number of possible games explodes to roughly 2 to the power of n/2 times 2 to the power of n/2 times 2 to the power of n/2 times 2 to the power of n/2, or 2 to the power of 2n. Since 2 to the power of 2n is 4 to the power of n, the complexity is O(4^n).

Space Complexity

O(N!) – The brute force solution explores all possible move combinations between Alice and Bob, building a game tree. In the worst-case scenario, the number of possible games grows factorially with the number of available numbers, N, where N is the number of unknown numbers in the initial input. Since each level of the game tree corresponds to a move, and we may need to store the state of the game (who picked what) at each node, the memory needed to construct this tree can grow proportionally to the number of possible game states. Thus, the space complexity is O(N!).

Optimal Solution

Approach

The Sum Game involves two players alternately picking numbers from a series to reach a target sum. The trick is to realize a winning strategy is about forcing a scenario rather than calculating all possibilities.

Here's how the algorithm would work step-by-step:

Figure out the total sum of all the numbers.
Find out the midpoint of the series - the point that divides the numbers in half.
Determine the difference between the sums of the two halves.
If Alice moves first and can guarantee the sums of both halves are equal after all the turns, Alice will win.
Alice's optimal strategy revolves around mirroring Bob's moves on the opposite side of the midpoint. For example, if Bob picks a number on the left side, Alice picks the corresponding number on the right side.
Check if Bob can force a condition where the sums cannot be made equal after Alice's move. If yes, then Bob wins.

Code Implementation

def sum_game(number_string):
    number_of_question_marks = number_string.count('?')
    string_length = len(number_string)

    if number_of_question_marks % 2 == 0:
        return False

    half_length = string_length // 2

    left_sum = 0
    left_question_marks = 0

    for i in range(half_length):
        if number_string[i] == '?':
            left_question_marks += 1
        else:
            left_sum += int(number_string[i])

    right_sum = 0
    right_question_marks = 0

    for i in range(half_length + 1, string_length):
        if number_string[i] == '?':
            right_question_marks += 1
        else:
            right_sum += int(number_string[i])

    # Crucial check: if the difference in sums is equal to half the difference in question marks * 9, Alice loses.
    if left_sum - right_sum == (right_question_marks - left_question_marks) * 9 / 2:
        return False
    # If the sums aren't equal after adjustment, Alice can win.
    else:
        return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The provided strategy focuses on calculating sums and differences, and determining the midpoint which involves basic arithmetic operations. There are no loops or recursion involved. Therefore, the execution time does not scale with the input size 'n'. All operations are performed in a fixed amount of time, resulting in O(1) time complexity.

Space Complexity

O(1) – The described algorithm calculates sums and differences without using any auxiliary data structures like lists or hash maps. It only stores a few variables to keep track of the sums of the two halves and the difference between them. Therefore, the amount of extra memory used remains constant regardless of the input size N, where N is the number of numbers in the series. The space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return false immediately since an empty string trivially satisfies the condition of equal sums.
Input string with only question marks	Alice loses if the number of question marks is equal on both halves since Bob can always mirror Alice's moves to create equal sums.
Input string with no question marks and equal sums	Return false because Alice loses as sums are already equal.
Input string with no question marks and unequal sums	Return true because Alice wins as sums are already unequal.
Input string with an odd number of question marks in each half	The difference in question marks will always be odd, meaning Alice can force the sum difference.
Integer overflow when calculating sums if the input string contains many digits	Use a larger integer type (e.g., long) to avoid overflow during sum calculation.
Input string with only digits in one half and only question marks in the other	Analyze the sum of the digit half, and determine if Alice can force inequality given the number of question marks.
Input string close to the maximum length (performance consideration)	Ensure the solution has linear time complexity O(n) to handle large inputs efficiently.