# Find if Digit Game Can Be Won
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-if-digit-game-can-be-won)
Canonical: https://scaleengineer.com/dsa/problems/find-if-digit-game-can-be-won
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## 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`.

**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`

# Approaches
## Two-Pass Iteration
This straightforward approach involves iterating through the input array twice. The first pass calculates the sum of all single-digit numbers, and the second pass calculates the sum of all double-digit numbers. Finally, it checks if either sum is strictly greater than the other, which would allow Alice to win.
**Time:** O(N), where N is the length of the `nums` array. The array is traversed twice, leading to a time complexity of O(N + N), which simplifies to O(N). · **Space:** O(1), as we only use a few variables to store the sums, regardless of the input size.
**Pros:** The logic is very clear and easy to follow, as the calculation for each group of numbers is handled separately.
**Cons:** It is inefficient as it requires two full passes over the input array, while one is sufficient.
### Explanation
The problem asks if Alice can win by choosing either all single-digit numbers or all double-digit numbers. A win occurs if the sum of her chosen numbers is strictly greater than the sum of the numbers left for Bob.

This can be broken down into two scenarios:
1.  **Alice chooses single-digit numbers:** Her sum is the total of all numbers from 1-9. Bob's sum is the total of all numbers from 10-99. She wins if `sum_single > sum_double`.
2.  **Alice chooses double-digit numbers:** Her sum is the total of all numbers from 10-99. Bob's sum is the total of all numbers from 1-9. She wins if `sum_double > sum_single`.

Alice wins the game if *either* of these scenarios results in a win for her. This is true if and only if the two sums are not equal (`sum_single != sum_double`).

This approach implements this logic by first calculating `sum_single` in one loop and then `sum_double` in a second loop before comparing them.

```java
class Solution {
    public boolean canAliceWin(int[] nums) {
        int sumSingleDigits = 0;
        // First pass: calculate the sum of all single-digit numbers.
        for (int num : nums) {
            if (num >= 1 && num <= 9) {
                sumSingleDigits += num;
            }
        }

        int sumDoubleDigits = 0;
        // Second pass: calculate the sum of all double-digit numbers.
        for (int num : nums) {
            if (num >= 10 && num <= 99) {
                sumDoubleDigits += num;
            }
        }

        // Alice wins if she can make a choice where her sum is strictly greater.
        // This is possible if the two sums are not equal.
        return sumSingleDigits != sumDoubleDigits;
    }
}
```
### Algorithm
- 1. Initialize a variable `sumSingleDigits` to 0.
- 2. Iterate through the `nums` array. For each number, if it's a single-digit number (i.e., less than 10), add it to `sumSingleDigits`.
- 3. Initialize a variable `sumDoubleDigits` to 0.
- 4. Iterate through the `nums` array again. For each number, if it's a double-digit number (i.e., 10 or greater), add it to `sumDoubleDigits`.
- 5. Check if Alice can win. This happens if her sum is strictly greater than Bob's.
- 6. If Alice chooses single-digit numbers, she wins if `sumSingleDigits > sumDoubleDigits`.
- 7. If Alice chooses double-digit numbers, she wins if `sumDoubleDigits > sumSingleDigits`.
- 8. Return `true` if either of these conditions is met, which simplifies to `sumSingleDigits != sumDoubleDigits`. Otherwise, return `false`.

## Single-Pass Iteration (Optimal)
This optimal approach improves upon the two-pass method by calculating the sums of both single-digit and double-digit numbers in a single iteration over the array. This minimizes the number of operations required.
**Time:** O(N), where N is the length of the `nums` array. Each element is visited exactly once. · **Space:** O(1), as the space used for the sum variables does not depend on the size of the input array.
**Pros:** Most efficient solution in terms of time complexity as it requires only one pass.; Code is concise and clean.
**Cons:** There are no significant drawbacks to this approach for this particular problem.
### Explanation
The fundamental logic is identical to the previous approach: Alice wins if the total sum of single-digit numbers is different from the total sum of double-digit numbers.

However, we can optimize the calculation by computing both sums at the same time. We can iterate through the `nums` array just once.

We maintain two running totals: `sumSingle` for numbers less than 10, and `sumDouble` for numbers 10 or greater.

During the single loop, we check each number and add it to the appropriate sum.

After the loop completes, we have both totals and can perform the final comparison. Alice wins if `sumSingle != sumDouble`. This method is more efficient as it avoids a second scan of the array.

```java
class Solution {
    public boolean canAliceWin(int[] nums) {
        int sumSingleDigits = 0;
        int sumDoubleDigits = 0;

        // Iterate through the array once to calculate both sums.
        for (int num : nums) {
            if (num < 10) {
                sumSingleDigits += num;
            } else {
                sumDoubleDigits += num;
            }
        }

        // Alice wins if the sum of single-digit numbers is not equal to
        // the sum of double-digit numbers. If they are different, she can
        // choose the group with the larger sum.
        return sumSingleDigits != sumDoubleDigits;
    }
}
```
### Algorithm
- 1. Initialize two variables, `sumSingleDigits` and `sumDoubleDigits`, to 0.
- 2. Iterate through the `nums` array in a single loop.
- 3. For each number `num` in the array:
    - If `num` is less than 10, add it to `sumSingleDigits`.
    - Otherwise, add it to `sumDoubleDigits`.
- 4. After the loop, compare the two sums.
- 5. Return `true` if `sumSingleDigits` is not equal to `sumDoubleDigits`. Otherwise, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean canAliceWin(int[] nums) {
    int a = 0, b = 0;
    for (int x : nums) {
      if (x < 10) {
        a += x;
      } else {
        b += x;
      }
    }
    return a != b;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canAliceWin(vector<int> &nums) {
    int a = 0, b = 0;
    for (int x : nums) {
      if (x < 10) {
        a += x;
      } else {
        b += x;
      }
    }
    return a != b;
  }
};

```

### Python

```python
class Solution:
    def canAliceWin(self, nums: List[int]) -> bool: a = sum(x for x in nums if x < 10) b = sum(x for x in nums if x > 9) return a != b

```