LeetCode 1927: Sum Game Solution

Master LeetCode problem 1927 (Sum Game), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1927. Sum Game

Medium

Math String Greedy Game Theory

Problem Explanation

Explanation

To determine the winner of the game, we need to analyze the possible outcomes by making optimal moves. The key observation is that the sum of the digits in the first half must be equal to the sum of the digits in the second half for Bob to win. Otherwise, Alice wins.

We can iterate through all possible combinations of replacing '?' characters with digits and check if there exists a valid move for Alice or Bob. If there is a move that guarantees a win for Alice, then Alice wins; otherwise, Bob wins.

Algorithm:

Count the number of '?' characters in the input string num.
Calculate the sum of the known digits in the first half and second half separately.
Iterate through all possible combinations of replacing '?' characters with digits.
If at any point, the sum of the first half is not equal to the sum of the second half, Alice wins.
If no such combination exists where Alice wins, Bob wins.

Time Complexity:

The time complexity of this approach is O(10^n) where n is the number of '?' characters in the input string.

Space Complexity:

The space complexity is O(n) where n is the length of the input string.

Solution Code

class Solution {
    public boolean sumGame(String num) {
        int n = num.length();
        int half = n / 2;
        int sum1 = 0, sum2 = 0, count = 0;
        
        for (int i = 0; i < n; i++) {
            char c = num.charAt(i);
            if (c == '?') {
                if (i < half) count++;
                else count--;
            } else {
                if (i < half) sum1 += (i < half) ? c - '0' : 0;
                else sum2 += (i < half) ? c - '0' : 0;
            }
        }
        
        if (count % 2 != 0) return true;
        
        count /= 2;
        for (int i = 0; i < n; i++) {
            char c = num.charAt(i);
            if (c == '?') {
                if (count > 0) {
                    sum1 += 9;
                    count--;
                } else {
                    sum2 += 9;
                }
            } else {
                if (i < half) sum1 += (i < half) ? c - '0' : 0;
                else sum2 += (i < half) ? c - '0' : 0;
            }
        }
        
        return sum1 != sum2;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1927 (Sum Game)?

This page provides optimized solutions for LeetCode problem 1927 (Sum Game) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1927 (Sum Game)?

The time complexity for LeetCode 1927 (Sum Game) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1927 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1927 in Java, C++, or Python.

Back to LeetCode Solutions