1927. Sum Game LeetCode Solution

In this guide, you will get 1927. Sum Game LeetCode Solution with the best time and space complexity. The solution to Sum Game problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sum Game solution in C++
Sum Game solution in Java
Sum Game solution in Python
Additional Resources

Problem Statement of Sum Game

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 <= 105
num.length is even.
num consists of only digits and '?'.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

1927. Sum Game LeetCode Solution in C++

class Solution {
 public:
  bool sumGame(string num) {
    const 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';
  }
};
/* code provided by PROGIEZ */

1927. Sum Game LeetCode Solution in Java

class Solution {
  public boolean sumGame(String num) {
    final int n = num.length();
    double ans = 0.0;

    for (int i = 0; i < n / 2; ++i)
      ans += getExpectation(num.charAt(i));

    for (int i = n / 2; i < n; ++i)
      ans -= getExpectation(num.charAt(i));

    return ans != 0.0;
  }

  private double getExpectation(char c) {
    return c == '?' ? 4.5 : c - '0';
  }
}
// code provided by PROGIEZ

1927. Sum Game LeetCode Solution in Python

class Solution:
  def sumGame(self, num: str) -> bool:
    n = len(num)
    ans = 0.0

    def getExpectation(c: str) -> float:
      return 4.5 if c == '?' else int(c)

    for i in range(n // 2):
      ans += getExpectation(num[i])

    for i in range(n // 2, n):
      ans -= getExpectation(num[i])

    return ans != 0.0
 # code by PROGIEZ