1927. Sum Game
Problem Description
In this game, two players, Alice and Bob, take turns modifying a string of even length containing digits and '?' characters, with Alice going first. Each turn consists of replacing a single '?' with a digit between '0' and '9'. The game concludes when no '?' characters remain in the string.
The objective for Bob to win is to have the sum of the digits in the first half of the final string equal to the sum of the digits in the second half. In contrast, Alice aims for these sums to be unequal.
The task is to determine whether Alice, assuming optimal play from both players, will win the game.
Intuition
This solution exploits the fact that each player will play optimally, meaning they will make the best possible move at each turn to maximize their chances of winning.
The two important factors analyzed here are the count of '?' characters (cnt1
and cnt2
) in both halves of the string and the sums (s1
and s2
) of known digits in each half at the start.
Observations to consider:
- If the total count of '?' is odd, then Alice will always win because Bob will be the last to play, contributing to an imbalance.
- If the sums differ by an amount that isn't exactly half of 9 times the difference in '?' count between the two halves, Alice can enforce a win by strategically placing digits to prevent Bob from balancing the sums.
The implementation checks for these two conditions to predict the winner, with the expression s1 - s2 != 9 * (cnt2 - cnt1) // 2
capturing the second observation.
By examining the parity of '?' and the sums' balance in relation to '?' distribution, the solution concludes who wins the game under optimal play.
Solution Approach
The solution approach leverages simple arithmetic and logical checks based on the initial configuration of the string.
Here is a step-by-step breakdown of how the algorithm works:
-
Determine '?' Counts and Partial Sums:
- The solution begins by splitting the string into two equal parts since the game's outcome depends on the comparison of these two segments.
- It counts the number of '?' characters in each half (denoted as
cnt1
for the first half, andcnt2
for the second half). - It calculates the sum of all known digits (ignoring '?') in each half (referred to as
s1
for the first half, ands2
for the second half).
-
Check Parity of '?' Characters:
- Since players alternate turns, if the total number of '?' is odd, it implies Alice will always have one extra turn. The parity check
(cnt1 + cnt2) % 2 == 1
asserts whether the number of '?' characters is odd, which would mean Alice wins.
- Since players alternate turns, if the total number of '?' is odd, it implies Alice will always have one extra turn. The parity check
-
Evaluate Sums Based on '?' Distribution:
- If parity is not the determining factor, the algorithm moves on to evaluate whether the difference in known sums (s1 and s2) can be balanced by the '?' characters.
- This is judged by
s1 - s2 != 9 * (cnt2 - cnt1) // 2
. The rationale is that each '?' can ultimately contribute a value between 0 to 9 when replaced by a digit. Bob's goal to balance the sums can be thwarted if the difference between s1 and s2 cannot be matched by strategically placing numbers where '?' exist. - Here,
9 * (cnt2 - cnt1) // 2
gives the maximum potential difference that Bob can cause by manipulating '?' (because 9 is the maximum possible number to add to the sum for each '?'). - If the actual difference
s1 - s2
does not equal half of the potential difference, it implies that Alice, by playing optimally, can always prevent the sums from equalling.
-
Return the Winner:
- The booleans returned by the checks outlined above directly feed into the final return statement. If any of the conditions is true, Alice wins (
True
). Otherwise, the game outcome is in favor of Bob (False
), meaning that he can balance the sums even with optimal play from Alice.
- The booleans returned by the checks outlined above directly feed into the final return statement. If any of the conditions is true, Alice wins (
The solution uses only basic data structures (integer variables for counting and summing) and relies mainly on arithmetic and conditional checks, showcasing a direct and efficient approach to predict the game's outcome.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have a string s
of even length: "5?2?". Alice and Bob will take turns replacing '?' with digits in order to achieve their objectives as described.
-
Determine '?' Counts and Partial Sums:
- The string is split into two equal halves: "5?" and "2?".
- The counts of '?' are determined:
cnt1
= 1 in the first half, andcnt2
= 1 in the second half. - The partial sums are calculated:
s1
= 5 in the first half, ands2
= 2 in the second half (ignoring '?').
-
Check Parity of '?' Characters:
- We check if the total number of '?' is odd:
(cnt1 + cnt2) % 2 == (1 + 1) % 2 == 0
. In this case, it is even, so this condition does not determine the winner.
- We check if the total number of '?' is odd:
-
Evaluate Sums Based on '?' Distribution:
- Since the parity is not odd, we evaluate whether the difference in sums can be balanced:
s1 - s2 != 9 * (cnt2 - cnt1) // 2
, which translates to5 - 2 != 9 * (1 - 1) // 2
. - This simplifies to
3 != 0
, which is true. This means the difference in the current sums (s1
ands2
) cannot be precisely offset by the '?' characters available because the difference in the number of '?' in each half is zero, so the maximum potential difference that Bob can cause is also zero. - Since the condition
s1 - s2 != 9 * (cnt2 - cnt1) // 2
is satisfied, it implies that Bob cannot make the sums equal regardless of how he plays.
- Since the parity is not odd, we evaluate whether the difference in sums can be balanced:
-
Return the Winner:
- The condition from step 3 ensures Alice's victory. So, the function would return
True
, indicating Alice wins the game with optimal play.
- The condition from step 3 ensures Alice's victory. So, the function would return
By following the solution approach, you can see how the initial set-up of the game allows us to predict the winner by using simple arithmetic and logical checks. In this example, even though Bob has an opportunity to place a number, he cannot balance the sums, guaranteeing Alice's victory.
Solution Implementation
1class Solution:
2 def sumGame(self, num: str) -> bool:
3 # Calculate the length of the string to divide it into two halves
4 length = len(num)
5
6 # Count occurrences of '?' in each half of the string
7 count_left = num[:length // 2].count("?")
8 count_right = num[length // 2:].count("?")
9
10 # Calculate the sum of digits in the left half, ignoring '?'
11 sum_left = sum(int(digit) for digit in num[:length // 2] if digit != "?")
12
13 # Calculate the sum of digits in the right half, ignoring '?'
14 sum_right = sum(int(digit) for digit in num[length // 2:] if digit != "?")
15
16 # There are two conditions that make the game start in a losing state:
17 # 1. The total number of '?' is odd, one player will always be at a disadvantage
18 # 2. The sum difference is not equal to half the 9 times the difference in '?' counts
19 # (since each '?' can contribute from 0 to 9 to the sum, the average contribution is 4.5)
20 return (count_left + count_right) % 2 == 1 or sum_left - sum_right != 9 * (count_right - count_left) // 2
21
22# The function can now be called with an instance of the Solution class and a numerical string as an argument
23# Example usage:
24# sol = Solution()
25# result = sol.sumGame("026??")
26# print(result) # Output will be either True or False based on the game's state
27
1class Solution {
2 public boolean sumGame(String num) {
3 int length = num.length();
4 int questionMarksLeftHalf = 0, questionMarksRightHalf = 0;
5 int sumLeftHalf = 0, sumRightHalf = 0;
6
7 // Loop through the left half of the string
8 for (int i = 0; i < length / 2; ++i) {
9 if (num.charAt(i) == '?') {
10 // Count question marks in the left half
11 questionMarksLeftHalf++;
12 } else {
13 // Sum the digits in the left half
14 sumLeftHalf += num.charAt(i) - '0';
15 }
16 }
17
18 // Loop through the right half of the string
19 for (int i = length / 2; i < length; ++i) {
20 if (num.charAt(i) == '?') {
21 // Count question marks in the right half
22 questionMarksRightHalf++;
23 } else {
24 // Sum the digits in the right half
25 sumRightHalf += num.charAt(i) - '0';
26 }
27 }
28
29 // Check if the total number of question marks is odd
30 boolean isOddNumberOfQuestionMarks = (questionMarksLeftHalf + questionMarksRightHalf) % 2 == 1;
31
32 // Check if the difference in sums is not equal to half the difference in counts of question marks * 9
33 boolean isSumDifferenceInvalid = sumLeftHalf - sumRightHalf != 9 * (questionMarksRightHalf - questionMarksLeftHalf) / 2;
34
35 // Determine the result of the game by using the calculated booleans
36 return isOddNumberOfQuestionMarks || isSumDifferenceInvalid;
37 }
38}
39
1class Solution {
2public:
3 bool sumGame(string num) {
4 int length = num.size(); // Store the length of the num string
5 int countLeft = 0, countRight = 0; // Initialize question mark counters for both halves
6 int sumLeft = 0, sumRight = 0; // Initialize sum counters for both halves
7
8 // Loop through the first half of the num string
9 for (int i = 0; i < length / 2; ++i) {
10 if (num[i] == '?') {
11 // Increase question mark count for the left half if encountered
12 countLeft++;
13 } else {
14 // Add the numeric value to the sum of the left half
15 sumLeft += num[i] - '0'; // Convert char to int
16 }
17 }
18
19 // Loop through the second half of the num string
20 for (int i = length / 2; i < length; ++i) {
21 if (num[i] == '?') {
22 // Increase question mark count for the right half if encountered
23 countRight++;
24 } else {
25 // Add the numeric value to the sum of the right half
26 sumRight += num[i] - '0'; // Convert char to int
27 }
28 }
29
30 // Check if the game cannot be made equal
31 // If the total number of '?' is odd, or if the sum difference is not equal to the difference in '?' count multiplied by 9 divided by 2
32 // then the game is not balanced and thus return true, else the game could end in a draw, so return false.
33 return (countLeft + countRight) % 2 == 1 || (sumLeft - sumRight) != 9 * (countRight - countLeft) / 2;
34 }
35};
36
1function sumGame(numString: string): boolean {
2 // Calculate the length of the input string
3 const length = numString.length;
4 // Initialize counters for question marks and sum of digits for both halves
5 let questionMarksLeft = 0, questionMarksRight = 0, sumLeft = 0, sumRight = 0;
6
7 // Iterate through the first half of the string
8 for (let i = 0; i < length / 2; ++i) {
9 if (numString[i] === '?') {
10 // Increment counter for question marks in the left half
11 ++questionMarksLeft;
12 } else {
13 // Add digit value to total sum of the left half
14 sumLeft += numString[i].charCodeAt(0) - '0'.charCodeAt(0);
15 }
16 }
17
18 // Iterate through the second half of the string
19 for (let i = length / 2; i < length; ++i) {
20 if (numString[i] === '?') {
21 // Increment counter for question marks in the right half
22 ++questionMarksRight;
23 } else {
24 // Add digit value to total sum of the right half
25 sumRight += numString[i].charCodeAt(0) - '0'.charCodeAt(0);
26 }
27 }
28
29 // Check if the total number of question marks is odd
30 // or if the double of the difference in sums is not equal to nine times the difference in question marks count
31 // The game is Alice's win if any of these conditions is true
32 return (questionMarksLeft + questionMarksRight) % 2 === 1 ||
33 2 * (sumLeft - sumRight) !== 9 * (questionMarksRight - questionMarksLeft);
34}
35
Time and Space Complexity
The time complexity of the given Python code can be broken down into several parts:
-
Calculating
n
: This is performed in constant time, so its complexity isO(1)
. -
Counting '?': The
count()
function is called twice, once on each half of the string. Since the string is of lengthn
, and it's divided into two halves, each of lengthn/2
, counting '?' on each half takesO(n/2)
, resulting in a total complexity ofO(n)
for both halves together. -
Summing digits: Similar to counting, summation is performed twice, once on each half of the string, excluding '?'. This also takes
O(n/2)
for each half, summing up toO(n)
for the whole string. -
The final
return
statement involves a comparison operation, which is done in constant timeO(1)
.
Considering all parts, the overall time complexity of the function is dominated by the counting and summing operations, which are linear with respect to the length of the string. Hence, the time complexity is O(n)
.
Regarding space complexity:
The additional space used by the function is for storing the temporary variables cnt1
, cnt2
, s1
, and s2
. These are constant size variables, and their space does not grow with the input size. Therefore, no matter how large n
gets, the space used remains constant, leading to a space complexity of O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!