Find if Digit Game Can Be Won
EasyPrompt
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 <= 1001 <= nums[i] <= 99
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
-
- Initialize a variable
sumSingleDigitsto 0.
- Initialize a variable
-
- Iterate through the
numsarray. For each number, if it's a single-digit number (i.e., less than 10), add it tosumSingleDigits.
- Iterate through the
-
- Initialize a variable
sumDoubleDigitsto 0.
- Initialize a variable
-
- Iterate through the
numsarray again. For each number, if it's a double-digit number (i.e., 10 or greater), add it tosumDoubleDigits.
- Iterate through the
-
- Check if Alice can win. This happens if her sum is strictly greater than Bob's.
-
- If Alice chooses single-digit numbers, she wins if
sumSingleDigits > sumDoubleDigits.
- If Alice chooses single-digit numbers, she wins if
-
- If Alice chooses double-digit numbers, she wins if
sumDoubleDigits > sumSingleDigits.
- If Alice chooses double-digit numbers, she wins if
-
- Return
trueif either of these conditions is met, which simplifies tosumSingleDigits != sumDoubleDigits. Otherwise, returnfalse.
- Return
Walkthrough
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:
- 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. - 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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
-
- Initialize two variables,
sumSingleDigitsandsumDoubleDigits, to 0.
- Initialize two variables,
-
- Iterate through the
numsarray in a single loop.
- Iterate through the
-
- For each number
numin the array:
- If
numis less than 10, add it tosumSingleDigits. - Otherwise, add it to
sumDoubleDigits.
- For each number
-
- After the loop, compare the two sums.
-
- Return
trueifsumSingleDigitsis not equal tosumDoubleDigits. Otherwise, returnfalse.
- Return
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 != bVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.