Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


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

Output: false

Explanation:

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

Example 2

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8


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

Solution

Method 1 – Greedy Sum Comparison

Intuition

The key idea is to split the numbers into single-digit and double-digit groups, then check if the sum of either group is strictly greater than the sum of the rest. Alice can only pick all single-digit or all double-digit numbers, so we just need to compare both options.

Approach

  1. Separate the numbers into single-digit (1-9) and double-digit (10-99) groups.
  2. Calculate the sum of each group and the total sum.
  3. For each group, check if its sum is strictly greater than the sum of the other group.
  4. Return true if either condition is met; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    bool digitGameCanBeWon(vector<int>& nums) {
        int s1 = 0, s2 = 0, total = 0;
        for (int n : nums) {
            total += n;
            if (n < 10) s1 += n;
            else s2 += n;
        }
        return s1 > total - s1 || s2 > total - s2;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func digitGameCanBeWon(nums []int) bool {
    s1, s2, total := 0, 0, 0
    for _, n := range nums {
        total += n
        if n < 10 {
            s1 += n
        } else {
            s2 += n
        }
    }
    return s1 > total-s1 || s2 > total-s2
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public boolean digitGameCanBeWon(int[] nums) {
        int s1 = 0, s2 = 0, total = 0;
        for (int n : nums) {
            total += n;
            if (n < 10) s1 += n;
            else s2 += n;
        }
        return s1 > total - s1 || s2 > total - s2;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun digitGameCanBeWon(nums: IntArray): Boolean {
        var s1 = 0; var s2 = 0; var total = 0
        for (n in nums) {
            total += n
            if (n < 10) s1 += n else s2 += n
        }
        return s1 > total - s1 || s2 > total - s2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def digitGameCanBeWon(self, nums: list[int]) -> bool:
        s1 = s2 = total = 0
        for n in nums:
            total += n
            if n < 10:
                s1 += n
            else:
                s2 += n
        return s1 > total - s1 or s2 > total - s2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn digit_game_can_be_won(nums: Vec<i32>) -> bool {
        let (mut s1, mut s2, mut total) = (0, 0, 0);
        for n in nums.iter() {
            total += n;
            if *n < 10 {
                s1 += n;
            } else {
                s2 += n;
            }
        }
        s1 > total - s1 || s2 > total - s2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    digitGameCanBeWon(nums: number[]): boolean {
        let s1 = 0, s2 = 0, total = 0;
        for (const n of nums) {
            total += n;
            if (n < 10) s1 += n;
            else s2 += n;
        }
        return s1 > total - s1 || s2 > total - s2;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We iterate through the array once.
  • 🧺 Space complexity: O(1), only a few integer variables are used for sums.