Problem Description

You have an array nums containing only positive integers. Alice and Bob are playing a game with these numbers.

The game rules are:

• Alice must choose either all single-digit numbers (1-9) or all double-digit numbers (10-99) from the array
• Bob gets all the remaining numbers that Alice didn't choose
• Alice wins if the sum of her chosen numbers is strictly greater than the sum of Bob's numbers

Your task is to determine if Alice can win this game. Return true if Alice has a winning strategy, otherwise return false.

For example, if nums = [1, 2, 3, 4, 10, 11]:

• Alice could choose all single-digit numbers: [1, 2, 3, 4] with sum = 10
• Bob would get the double-digit numbers: [10, 11] with sum = 21
• Since 10 < 21, Alice loses with this choice
• Alternatively, Alice could choose all double-digit numbers: [10, 11] with sum = 21
• Bob would get the single-digit numbers: [1, 2, 3, 4] with sum = 10
• Since 21 > 10, Alice wins with this choice

The solution recognizes that Alice can win as long as the sum of single-digit numbers is different from the sum of double-digit numbers. When these sums are different, Alice will simply choose whichever group has the larger sum to guarantee her victory.

Intuition

Let's think about what Alice's options are. She has exactly two choices:

1. Take all single-digit numbers
2. Take all double-digit numbers

Since Alice gets to choose first and she wants to win, she will naturally pick whichever option gives her the larger sum.

Let's denote:

• a = sum of all single-digit numbers
• b = sum of all double-digit numbers

If Alice chooses single-digit numbers, she gets a and Bob gets b. Alice wins if a > b.

If Alice chooses double-digit numbers, she gets b and Bob gets a. Alice wins if b > a.

The key insight is that Alice can win if and only if a ≠ b. Why?

• If a > b, Alice chooses single-digit numbers and wins
• If b > a, Alice chooses double-digit numbers and wins
• If a = b, no matter what Alice chooses, she gets the same sum as Bob, resulting in a tie (not a win)

Since Alice needs to win strictly (her sum must be greater, not equal), she cannot win when a = b.

This leads us to the elegant solution: simply calculate the sum of single-digit numbers and the sum of double-digit numbers. If they're different, Alice can win by choosing the larger group. If they're equal, Alice cannot win.

Learn more about Math patterns.

Solution Approach

The implementation is straightforward based on our intuition. We need to:

1. Calculate the sum of all single-digit numbers (numbers less than 10)
2. Calculate the sum of all double-digit numbers (numbers greater than or equal to 10)
3. Check if these two sums are different

Here's how the solution works:

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        a = sum(x for x in nums if x < 10)
        b = sum(x for x in nums if x > 9)
        return a != b

Step-by-step breakdown:

1. Calculate sum of single-digit numbers: a = sum(x for x in nums if x < 10)

   • We use a generator expression with list comprehension to filter numbers less than 10
   • The sum() function adds up all these single-digit numbers

2. Calculate sum of double-digit numbers: b = sum(x for x in nums if x > 9)

   • Similarly, we filter numbers greater than 9 (which are the double-digit numbers)
   • Sum all these double-digit numbers

3. Determine if Alice can win: return a != b

   • If the sums are different (a != b), Alice can choose the larger group and win
   • If the sums are equal (a == b), Alice cannot win regardless of her choice

Time Complexity: O(n) where n is the length of the array, as we iterate through the array once to calculate both sums.

Space Complexity: O(1) as we only use two variables to store the sums, regardless of input size.

Example Walkthrough

Let's walk through a concrete example to see how this solution works.

Example: nums = [5, 17, 3, 20, 8, 12]

Step 1: Identify and sum single-digit numbers

• Single-digit numbers (< 10): [5, 3, 8]
• Sum of single-digit numbers: a = 5 + 3 + 8 = 16

Step 2: Identify and sum double-digit numbers

• Double-digit numbers (≥ 10): [17, 20, 12]
• Sum of double-digit numbers: b = 17 + 20 + 12 = 49

Step 3: Check if Alice can win

• Compare the sums: a = 16 and b = 49
• Since 16 ≠ 49, Alice can win!
• Alice's winning strategy: Choose the double-digit numbers to get sum = 49
• Bob gets the single-digit numbers with sum = 16
• Alice wins because 49 > 16

What if the sums were equal?

Consider nums = [5, 2, 3, 10]:

• Single-digit sum: 5 + 2 + 3 = 10
• Double-digit sum: 10
• Since both sums equal 10, no matter what Alice chooses, she gets 10 and Bob gets 10
• It's a tie, not a win, so the function returns false

The beauty of this solution is that we don't need to explicitly check both scenarios. We just need to verify that the sums are different, because Alice will intelligently pick whichever group gives her the advantage.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the code iterates through the entire array twice - once to calculate the sum of single-digit numbers (x < 10) and once to calculate the sum of double-digit numbers (x > 9). Even though there are two iterations, they are sequential and not nested, resulting in O(n) + O(n) = O(2n) = O(n) time complexity.

The space complexity is O(1). The code only uses two variables a and b to store the sums, which require constant space regardless of the input size. The generator expressions (x for x in nums if x < 10) and (x for x in nums if x > 9) are evaluated lazily and don't create intermediate lists, so they don't consume additional space proportional to the input size.

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

Common Pitfalls

1. Misunderstanding the Problem Constraints

Pitfall: Assuming the array only contains numbers from 1-99, when the problem states "positive integers" which could include numbers ≥ 100.

Issue Example:

# Incorrect assumption
def canAliceWin(self, nums: List[int]) -> bool:
    single_sum = sum(x for x in nums if x < 10)
    double_sum = sum(x for x in nums if x >= 10 and x <= 99)  # Wrong!
    return single_sum != double_sum

Solution: The problem states Alice chooses either single-digit (1-9) OR double-digit (10-99) numbers. Any number ≥ 100 automatically goes to Bob regardless of Alice's choice. The correct approach treats all numbers ≥ 10 as part of the "double-digit" group for calculation purposes:

def canAliceWin(self, nums: List[int]) -> bool:
    single_sum = sum(x for x in nums if x < 10)
    # Include ALL numbers >= 10, not just 10-99
    double_sum = sum(x for x in nums if x >= 10)
    return single_sum != double_sum

2. Off-by-One Error in Boundary Conditions

Pitfall: Using incorrect comparison operators for single vs. double-digit classification.

Issue Example:

# Incorrect boundaries
def canAliceWin(self, nums: List[int]) -> bool:
    single_sum = sum(x for x in nums if x <= 9)  # Includes 0 if present
    double_sum = sum(x for x in nums if x > 10)  # Excludes 10!
    return single_sum != double_sum

Solution: Use precise boundaries:

• Single-digit: 1 <= x <= 9 or simply x < 10 (assuming positive integers)
• Double-digit and above: x >= 10

3. Incorrect Win Condition Logic

Pitfall: Returning the wrong boolean condition or misunderstanding when Alice wins.

Issue Example:

# Wrong logic
def canAliceWin(self, nums: List[int]) -> bool:
    single_sum = sum(x for x in nums if x < 10)
    double_sum = sum(x for x in nums if x >= 10)
    return single_sum > double_sum  # Wrong! Alice can choose either group

Solution: Alice wins if she CAN make a choice that gives her a higher sum. This happens when the sums are different (she'll choose the larger one):

return single_sum != double_sum  # Correct