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. In the game, Alice can choose either all single-digit numbers or all double-digit numbers from nums, and the rest of the numbers are given to Bob. Alice wins if the sum of her numbers is strictly greater than the sum of Bob's numbers. Return true if Alice can win this game, otherwise, return false.

Key Insights

• Alice can choose either single-digit or double-digit numbers.
• The goal is for Alice's sum to exceed Bob's sum.
• The sum of all numbers can be divided into single-digit and double-digit sums.
• The total sum of numbers minus Alice's chosen sum gives Bob's sum.

Space and Time Complexity

Time Complexity: O(n) - We loop through the list once to calculate sums.
Space Complexity: O(1) - We use a constant amount of extra space.

Solution

To solve this problem, we can follow these steps:

1. Initialize two sums: sum_single_digits for single-digit numbers and sum_double_digits for double-digit numbers.
2. Iterate through the array nums, adding each number to the appropriate sum based on whether it is a single-digit or double-digit number.
3. Calculate Bob's sum as total_sum - chosen_sum, where chosen_sum is either sum_single_digits or sum_double_digits.
4. Check if Alice's chosen sum is greater than Bob's sum for both scenarios. If either is true, return true; otherwise, return false.

Code Solutions