#3232

Easy

LeetCode Problem Workspace

Find if Digit Game Can Be Won

Determine if Alice can guarantee a win in a game by selectively summing single or double-digit numbers from an array.

Problem Statement

You are given an array of positive integers called nums. Two players, Alice and Bob, take turns in a game where Alice can select either all single-digit numbers or all double-digit numbers from nums, and Bob receives the remaining numbers.

Alice wins if the sum of her selected numbers is strictly greater than the sum of Bob's numbers. Return true if Alice has a strategy to win, otherwise return false. Consider array patterns and the effect of summing single versus double-digit numbers.

Examples

Example 1

Input: nums = [1,2,3,4,10]

Output: false

Alice cannot win by choosing either single-digit or double-digit numbers.

Example 2

Input: nums = [1,2,3,4,5,14]

Output: true

Alice can win by choosing single-digit numbers which have a sum equal to 15.

Example 3

Input: nums = [5,5,5,25]

Output: true

Alice can win by choosing double-digit numbers which have a sum equal to 25.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 99

Solution Approach

Separate Numbers by Digit Count

Scan the nums array and separate numbers into single-digit and double-digit groups. This aligns directly with the game rule that Alice must pick one group entirely.

Compute Sums Efficiently

Calculate the sum of single-digit numbers and the sum of double-digit numbers. Comparing these totals with Bob's potential sum identifies if Alice can secure a win without iterating over all combinations.

Decision Based on Maximum Sum

Compare the sums: if the sum of single-digit numbers exceeds the sum of double-digit numbers assigned to Bob, or vice versa, return true. Otherwise, Alice cannot win, and return false. This uses the array plus math pattern directly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each number is inspected once to separate digits and compute sums. Space complexity is O(n) for storing single and double-digit groups, though it can be reduced to O(1) with running totals.

What Interviewers Usually Probe

Pay attention to array partitioning by single and double-digit numbers.
Notice that summing all numbers of one type is faster than testing combinations.
Check boundary cases like all numbers being single-digit or double-digit.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly identify single versus double-digit numbers in the array.
Attempting unnecessary subset sums instead of total sums of each group.
Overlooking edge cases where sums are equal, which does not allow Alice to win.

Follow-up variants

Allow Alice to pick any numbers whose digit count is prime instead of single/double digits.
Change the winning condition to sum difference >= k instead of strictly greater.
Include negative numbers in nums to see how sum comparison logic adapts.

FAQ

What strategy ensures Alice can win in the Digit Game?

Alice can guarantee a win by selecting either all single-digit or all double-digit numbers if their total sum exceeds Bob's remaining sum.

How do I handle arrays where sums are equal?

If the sum of chosen numbers equals Bob's sum, Alice cannot win because the condition requires a strictly greater total.

Does the array length affect the solution approach?

No, the approach is linear in array length; you just separate numbers by digit count and sum them.

Can Alice mix single and double-digit numbers?

No, the rules only allow selecting all numbers of one digit type, making the decision straightforward with sums.

Which problem pattern does this exercise focus on?

This problem exemplifies the Array plus Math pattern, emphasizing sum calculations over subsets for decision-making.

terminal

Solution

Solution 1: Summation

According to the problem description, as long as the sum of the units digits is not equal to the sum of the tens digits, Alice can always choose a larger sum to win.

1

2

3

4

5

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

Continue Practicing

#3233 find the count of numbers which are not special #3235 check if the rectangle corner is reachable #3250 find the count of monotonic pairs i