Skip to main content
Talentd

Find if Digit Game Can Be Won - Solution & Explanation

EasyArrayMath14 min read
Practice this problem

Problem Statement

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.

 

Example 1:

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

Output: false

Explanation:

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

Example 2:

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

Output: true

Explanation:

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

Explanation:

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

 

Constraints:

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

Approach Overview

Problem Overview: You are given an array of integers where each value is either a one-digit number (1–9) or a two-digit number (10–99). Alice chooses one category of numbers (all one-digit or all two-digit). Bob receives the remaining numbers. The goal is to determine if Alice can pick a category whose total sum is strictly greater than Bob’s.

Approach 1: Sum Calculation Approach (O(n) time, O(1) space)

Scan the array once and compute two running totals: sumSingle for one-digit numbers and sumDouble for two-digit numbers. If Alice chooses the one-digit group, her score becomes sumSingle and Bob gets sumDouble. If she chooses the two-digit group, the roles reverse. Alice wins if her chosen sum is strictly larger than Bob’s. This means the game is winnable whenever sumSingle != sumDouble. The implementation uses a single pass through the array and constant extra variables, giving linear time and constant space.

Approach 2: Categorize and Compare (O(n) time, O(1) space)

Another way to view the same logic is explicit categorization. Iterate through the array and classify each value based on digit count: numbers less than 10 go into the single-digit category, while the rest go into the two-digit category. Accumulate the sums for each category during the iteration. After processing all elements, compare the two totals. If the sums are equal, any choice Alice makes results in a tie with Bob, so she cannot win. If the sums differ, Alice simply selects the larger category and wins. The key insight is recognizing that the decision reduces to a simple comparison derived from basic math rather than simulating gameplay.

Recommended for interviews: The Sum Calculation approach is what interviewers expect. It demonstrates that you quickly reduce the problem to a simple arithmetic comparison after one pass through the array. Explaining both possible choices for Alice and showing that the condition simplifies to sumSingle != sumDouble proves you understand the reasoning rather than just implementing a loop.

Approach 1: Sum Calculation Approach

In this approach, we iterate over the array to calculate the sum of single-digit numbers and double-digit numbers separately. Alice then selects either the sum of single-digit numbers or the sum of double-digit numbers, trying to maximize her advantage. We compare these sums with each other, and Bob's sum is the difference between the total sum and Alice's chosen sum. Alice wins if her chosen sum is greater than Bob's sum.

This Python solution iterates over the list to sum up single- and double-digit numbers. It then checks both possible scenarios for Alice (choosing single or double digits) to see if her sum exceeds what Bob would get.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array. This is because we iterate over the array to calculate sums.
Space Complexity: O(1), as we use a constant amount of space.

Try this approach in the editor →

Approach 2: Categorize and Compare

This approach involves categorizing the numbers into single-digit and double-digit lists. We then calculate their sums and compare them against Bob's sum of the remaining numbers to see if Alice can win with any of these groupings.

This Python code checks whether the sum of single-digit or double-digit numbers is greater than the sum of the remaining numbers. This determines if Alice can win.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n). We perform summation over the array.
Space Complexity: O(1). Only a few integer variables are used.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sum Calculation Approach

Time Complexity: O(n), where n is the number of elements in the array. This is because we iterate over the array to calculate sums.
Space Complexity: O(1), as we use a constant amount of space.

Categorize and Compare

Time Complexity: O(n). We perform summation over the array.
Space Complexity: O(1). Only a few integer variables are used.

Summation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sum Calculation ApproachO(n)O(1)Best general solution; single pass computing sums of one-digit and two-digit numbers.
Categorize and CompareO(n)O(1)Useful when explicitly grouping numbers by digit length before comparing totals.

Video Solution

Leetcode Weekly Contest 408 || Problems A, B, C, || 3232, 3233, 3234 || Codeatic • Code-a-tic • 995 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find if Digit Game Can Be Won easy or hard?
Find if Digit Game Can Be Won is categorized as an Easy problem. The core idea is recognizing that Alice wins whenever the sum of one-digit numbers and two-digit numbers are not equal, which can be checked with a single array pass.
Find if Digit Game Can Be Won Python/Java solution
The implementation in Python or Java follows the same pattern: loop through the array, add numbers less than 10 to one sum and the rest to another, then return whether the two sums differ. The logic is identical across languages and runs in O(n) time.
How to solve Find if Digit Game Can Be Won in O(n)?
Iterate through the array and maintain two variables: one for the sum of numbers less than 10 and another for numbers greater than or equal to 10. After the loop, compare the two sums. If they are different, Alice selects the larger group and wins.
What is the best approach for Find if Digit Game Can Be Won?
The best approach is to compute the sum of one-digit numbers and the sum of two-digit numbers in a single pass through the array. Alice can win if the two sums are not equal because she can choose the category with the larger total. This solution runs in O(n) time with O(1) space.
Is Find if Digit Game Can Be Won asked at Google/Amazon/Meta?
Problems of this style appear frequently in interviews at companies like Amazon and Google because they test basic array traversal and logical reasoning. The difficulty is Easy, but interviewers often use it to evaluate clarity of thought and edge-case handling.
What data structure is used in Find if Digit Game Can Be Won?
The problem primarily uses a simple array traversal. No advanced data structures are required—only a few integer variables to track category sums during iteration.
What is the time complexity of Find if Digit Game Can Be Won?
The optimal solution runs in O(n) time because you scan the array once to compute two sums. Only a few integer variables are used, so the space complexity remains O(1).

Ready to solve this problem?

Practice Find if Digit Game Can Be Won with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Integers With Even Digit Sum

Next

Find Numbers with Even Number of Digits