Find if Digit Game Can Be Won - Video Solutions

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.