3232. Find if Digit Game Can Be Won

Problem Description

You are given an array of positive integers nums. Alice and Bob are playing a game where Alice can choose either all single-digit numbers or all double-digit numbers from nums. Bob receives the numbers not chosen by Alice. Alice wins if the sum of her chosen numbers is strictly greater than the sum of Bob's chosen numbers. The goal is to determine if Alice can win the game. Return true if Alice can win, otherwise return false.

Intuition

The key to the problem is to recognize that the game is based on selecting groups of numbers with specific properties: single-digit and double-digit numbers. Alice can choose to select numbers from one of these groups, while the remaining numbers go to Bob. For Alice to have the possibility of winning, the sum of these chosen numbers should be greater than the sum of the numbers chosen by Bob.

The solution leverages this by calculating the sum of single-digit numbers and the sum of double-digit numbers. By comparing these two sums, if they are not equal, Alice can always choose the group with the larger sum to ensure her victory.

The reasoning is simple: since the problem asks if Alice can win—which means selecting the larger sum—checking for inequality between both sums (a != b) suffices. If the sums are different, Alice has a winning choice no matter which group she selects.

Learn more about Math patterns.

Solution Approach

The problem can be solved using a straightforward summation approach. Here's the breakdown of how the solution is implemented:

Calculate the Sum of Single-Digit Numbers: Utilize a generator expression to iterate through the nums array and sum all numbers that are less than 10. This gives the total sum of single-digit numbers, denoted as a.
```
a = sum(x for x in nums if x < 10)
```
Calculate the Sum of Double-Digit Numbers: Similarly, use another generator expression to sum all numbers greater than 9. This is the sum of double-digit numbers, denoted as b.
```
b = sum(x for x in nums if x > 9)
```
Determine the Winner: Compare the two sums, a and b. Alice can win if the sums are not equal, which means there exists a strategy for Alice to choose the larger sum group. Therefore, return True if a is not equal to b, indicating Alice has a winning move.
```
return a != b
```

The logic ensures that as long as the sums of single-digit and double-digit numbers are different, Alice will always have the opportunity to choose the larger sum, ensuring her win.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with the array nums = [5, 12, 7, 22, 3]. We'll walk through the solution approach step-by-step:

Identify Single-Digit Numbers:
- From the array, identify all single-digit numbers: [5, 7, 3].
- Calculate their sum, a:
  - a = 5 + 7 + 3 = 15.
Identify Double-Digit Numbers:
- Identify all double-digit numbers in the array: [12, 22].
- Calculate their sum, b:
  - b = 12 + 22 = 34.
Determine if Alice Can Win:
- Compare the sums a and b:
  - Since 15 (sum of single-digit numbers) is not equal to 34 (sum of double-digit numbers), Alice can choose the set with the larger sum, which is the double-digit numbers [12, 22].
- Thus, the result of the function would be True, indicating that Alice can win the game by selecting the larger sum.

By following this logic, we ensure that if there is a difference in the sums, Alice can always choose the group with the larger sum to win the game.

Solution Implementation

1from typing import List
2
3class Solution:
4    # Method to determine if Alice can win based on the sum of numbers in the list
5    def canAliceWin(self, nums: List[int]) -> bool:
6        # Calculate the sum of numbers less than 10
7        sum_less_than_10 = sum(x for x in nums if x < 10)
8      
9        # Calculate the sum of numbers greater than 9
10        sum_greater_than_9 = sum(x for x in nums if x > 9)
11      
12        # Return True if the sums are not equal, indicating Alice can win
13        return sum_less_than_10 != sum_greater_than_9
14

1class Solution {
2    public boolean canAliceWin(int[] nums) {
3        int sumSmallNumbers = 0; // Sum of numbers less than 10
4        int sumLargeNumbers = 0; // Sum of numbers 10 or larger
5
6        // Iterate over each number in the array
7        for (int number : nums) {
8            // Check if the number is less than 10
9            if (number < 10) {
10                sumSmallNumbers += number; // Add to sumSmallNumbers if less than 10
11            } else {
12                sumLargeNumbers += number; // Add to sumLargeNumbers if 10 or more
13            }
14        }
15
16        // Return true if the sums are not equal, indicating Alice can win
17        return sumSmallNumbers != sumLargeNumbers;
18    }
19}
20

1class Solution {
2public:
3    bool canAliceWin(vector<int>& nums) {
4        int aliceSum = 0, bobSum = 0; // Initialize sums for Alice and Bob
5
6        // Iterate through the numbers in the vector
7        for (int number : nums) {
8            if (number < 10) { // If number is less than 10
9                aliceSum += number; // Add to Alice's sum
10            } else { // If number is 10 or greater
11                bobSum += number; // Add to Bob's sum
12            }
13        }
14
15        // Return true if Alice's sum is not equal to Bob's sum, implying one has more points
16        return aliceSum != bobSum;
17    }
18};
19

1// Function to determine if Alice can win
2function canAliceWin(nums: number[]): boolean {
3    // Initialize variables to hold the sum of specific elements
4    let sumLessThan10 = 0;  // Sum of numbers less than 10
5    let sum10OrMore = 0;    // Sum of numbers 10 or greater
6
7    // Iterate over each number in the nums array
8    for (const num of nums) {
9        // Add the number to the respective sum based on its value
10        if (num < 10) {
11            sumLessThan10 += num;
12        } else {
13            sum10OrMore += num;
14        }
15    }
16
17    // Return true if the sums are not equal, which means Alice can win
18    return sumLessThan10 !== sum10OrMore;
19}
20

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums, as each element is checked once to determine which sum it contributes to. The space complexity is O(1) because no additional space proportional to the input size is used; only a fixed amount of space is needed for the variables a and b.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don’t know