LeetCode 3232 - Find if Digit Game Can Be Won

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem presents a simple two-player game between Alice and Bob using an array of positive integers. Each number in the array is either a single-digit number (1 to 9) or a double-digit number (10 to 99). Alice has the choice to select either all single-digit numbers or all double-digit numbers from the array, while Bob automatically gets the remaining numbers. Alice wins if the sum of her selected numbers is strictly greater than Bob's sum. The task is to determine whether Alice can make a selection that allows her to win.

The input nums is an array of integers with a maximum length of 100, and each number is between 1 and 99 inclusive. The expected output is a boolean value: true if Alice can win, false otherwise.

Key edge cases include arrays where all numbers are single-digit or all numbers are double-digit, arrays where the sums of single-digit and double-digit numbers are equal, and arrays with only one element. The problem guarantees positive integers, so we do not need to handle zero or negative numbers.

Approaches

A brute-force approach would involve enumerating all possible ways Alice could select numbers, calculating the sum for each selection, and comparing it to Bob's sum. While this would work, it is unnecessarily complex because the problem explicitly limits Alice's options to only two deterministic choices: all single-digit numbers or all double-digit numbers. Since there are only two sums to compare, we do not need any advanced search.

The optimal approach leverages this observation. We first split the numbers into two groups based on whether they are single-digit or double-digit. We compute the sum of each group. Alice can win if either the sum of single-digit numbers is greater than the sum of double-digit numbers or vice versa. This direct approach is simple, linear, and sufficient for the problem constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerate all subsets of single-digit/double-digit numbers, inefficient
Optimal	O(n)	O(1)	Split numbers into single- and double-digit sums and compare

Algorithm Walkthrough

Initialize two integer variables, sum_single and sum_double, to zero. These will store the sums of single-digit and double-digit numbers, respectively.
Iterate through each number num in the input array nums.
For each number, check whether it is a single-digit number (less than 10). If so, add it to sum_single.
Otherwise, the number is double-digit (10 to 99), so add it to sum_double.
After processing all numbers, compare the sums. If sum_single is strictly greater than sum_double, return true. This indicates Alice wins by choosing single-digit numbers.
If sum_double is strictly greater than sum_single, return true. This indicates Alice wins by choosing double-digit numbers.
If neither sum is strictly greater, return false. Alice cannot win with either choice.

Why it works: The algorithm directly implements the rules of the game. Since Alice can only pick all single-digit numbers or all double-digit numbers, we only need to compare the two possible sums against the remainder. This ensures correctness while maintaining optimal efficiency.

Python Solution

from typing import List

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        sum_single = 0
        sum_double = 0
        
        for num in nums:
            if num < 10:
                sum_single += num
            else:
                sum_double += num
        
        return sum_single > sum_double or sum_double > sum_single

In this implementation, we iterate through the list once, categorizing each number as single-digit or double-digit and adding it to the respective sum. At the end, a simple comparison determines if Alice can win by choosing either group. This matches the algorithm steps exactly.

Go Solution

func canAliceWin(nums []int) bool {
    sumSingle := 0
    sumDouble := 0
    
    for _, num := range nums {
        if num < 10 {
            sumSingle += num
        } else {
            sumDouble += num
        }
    }
    
    return sumSingle > sumDouble || sumDouble > sumSingle
}

The Go version mirrors the Python logic. We use range to iterate through the slice. Variables are initialized to zero, and sums are accumulated similarly. The return statement directly checks the two possible winning conditions for Alice.

Worked Examples

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

num	sum_single	sum_double
1	1	0
2	3	0
3	6	0
4	10	0
10	10	10

Comparison: sum_single = 10, sum_double = 10 → neither is strictly greater → return false.

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

num	sum_single	sum_double
1	1	0
2	3	0
3	6	0
4	10	0
5	15	0
14	15	14

Comparison: sum_single = 15, sum_double = 14 → sum_single > sum_double → return true.

Example 3: nums = [5,5,5,25]

num	sum_single	sum_double
5	5	0
5	10	0
5	15	0
25	15	25

Comparison: sum_double = 25, sum_single = 15 → sum_double > sum_single → return true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate once through all numbers in `nums` to compute the sums.
Space	O(1)	Only two integer variables are used regardless of input size.

This linear time and constant space solution is optimal given the constraints.

Test Cases

# Provided examples
assert Solution().canAliceWin([1,2,3,4,10]) == False  # sums equal
assert Solution().canAliceWin([1,2,3,4,5,14]) == True  # Alice wins with single-digit
assert Solution().canAliceWin([5,5,5,25]) == True  # Alice wins with double-digit

# Edge cases
assert Solution().canAliceWin([1]) == True  # only one single-digit
assert Solution().canAliceWin([10]) == True  # only one double-digit
assert Solution().canAliceWin([9,10]) == False  # sums equal
assert Solution().canAliceWin([1,1,1,1,1,50]) == True  # Alice wins with double-digit
assert Solution().canAliceWin([9,9,9,9,9]) == True  # only single-digits, Alice wins
assert Solution().canAliceWin([10,20,30,40]) == True  # only double-digits, Alice wins

Test	Why
[1,2,3,4,10]	Sums equal, Alice cannot win
[1,2,3,4,5,14]	Alice can win by single-digit numbers
[5,5,5,25]	Alice can win by double-digit numbers
[1]	Single-element edge case
[10]	Single-element double-digit
[9,10]	Equal sums edge case
[1,1,1,1,1,50]	Large double-digit outweighs single-digit
[9,9,9,9,9]	Only single-digit numbers
[10,20,30,40]	Only double-digit numbers

Edge Cases

One important edge case is an array with a single element. If the single element is single-digit or double-digit, Alice automatically wins because Bob has nothing. The implementation handles this correctly because the sum of the non-chosen group is zero, which is less than Alice's sum.

Another edge case is when the sums of single-digit and double-digit numbers are equal. This could occur in arrays like [9,10] or [1,2,3,4,10]. Alice cannot win in this scenario. The algorithm correctly returns false because it only returns true when a sum is strictly greater.

A third edge case is when one group dominates by a large margin. For example, [1,1,1,1,50]. Alice should pick the double-digit number to win. The implementation correctly computes both sums and chooses the option with the strictly larger sum, ensuring correct handling of such disparities.