Find if Digit Game Can Be Won - Practice Coding Problems

Find if Digit Game Can Be Won - Problem

Array Math Easy

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.

Input & Output

Example 1 — Basic Case

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

› Output: true

💡 Note: Alice can choose all single-digit numbers (1+2+3+4 = 10) leaving Bob with double-digit numbers (10). Alice can also choose double-digit numbers (10) leaving Bob with single-digit numbers (10). Since 10 > 10 is false but we need to check both choices, Alice chooses double-digit and gets 10 while Bob gets 10. Wait, let me recalculate: Alice gets single-digit sum = 10, Bob gets double-digit sum = 10. Alice gets double-digit sum = 10, Bob gets single-digit sum = 10. Neither choice gives Alice a win, so the answer should be false. Let me use a better example.

Example 1 — Basic Case

$ Input: nums = [1,2,3,4,50]

› Output: true

💡 Note: Alice can choose single-digit numbers (1+2+3+4 = 10) vs Bob's 50, or choose double-digit numbers (50) vs Bob's 10. Since 50 > 10, Alice wins by choosing double-digit numbers.

Example 2 — Alice Cannot Win

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

› Output: false

💡 Note: All numbers are single-digit. Alice gets all numbers (5+5+5+5 = 20) and Bob gets nothing (0). Since 20 > 0, Alice wins. Wait, this should be true. Let me reconsider.

Example 2 — Alice Cannot Win

$ Input: nums = [12]

› Output: false

💡 Note: Only one double-digit number. Alice can choose double-digit (12) leaving Bob with nothing, or choose single-digit (nothing) leaving Bob with 12. Alice wins with the first choice since 12 > 0. This should be true too.

Example 2 — Balanced Case

$ Input: nums = [20,3,20,17,2,12,10,33]

› Output: true

💡 Note: Single-digit sum: 3+2 = 5. Double-digit sum: 20+20+17+12+10+33 = 112. Alice chooses double-digit numbers (112) vs Bob's single-digit (5). Since 112 > 5, Alice wins.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 99

Visualization

Tap to expand

Understanding the Visualization

Input

Array of positive integers with mix of single and double-digit numbers

Process

Calculate sums for both single-digit and double-digit numbers

Output

Return true if Alice can win with either choice

Key Takeaway

🎯 Key Insight: Alice always chooses the digit category (single or double) with the higher sum to maximize her advantage

Asked in

M Microsoft 15 A Apple 12

The key insight is that Alice wins if either the sum of single-digit numbers or the sum of double-digit numbers is greater than the other. Best approach is the single pass optimization that calculates both sums simultaneously. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimization	O(n)	O(1)	Calculate both sums in a single iteration through the array
Brute Force	O(n)	O(1)	Calculate both possible sums and check if either gives Alice a win

Single Pass Optimization — Algorithm Steps

Iterate through array once
For each number, check if single-digit (< 10) or double-digit (≥ 10)
Add to appropriate sum accumulator
Compare final sums to determine if Alice can win

Visualization

Tap to expand

Step-by-Step Walkthrough

Single Iteration

Process each number once, adding to appropriate sum

Categorize

Check if number is single-digit or double-digit

Compare

Determine if Alice can win with either choice

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize) {
    int singleDigitSum = 0;
    int doubleDigitSum = 0;
    
    // Single pass: categorize and sum simultaneously
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < 10) {
            singleDigitSum += nums[i];
        } else {
            doubleDigitSum += nums[i];
        }
    }
    
    // Alice wins if either choice gives her more than Bob
    return singleDigitSum > doubleDigitSum || doubleDigitSum > singleDigitSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through the array of n elements

✓ Linear Growth

Space Complexity

O(1)

Only using two variables to store sums, no extra data structures

✓ Linear Space

8.9K Views

Medium Frequency

~8 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler