Find if Digit Game Can Be Won solution and explanation
9 more videos on this problem
Leetcode Weekly Contest 408 || Problems A, B, C, || 3232, 3233, 3234 || CodeaticCode-a-tic · 47:30 · 995 views
Leetcode | 3232. Find if Digit Game Can Be Won | Easy | Java SolutionDeveloper Docs · 3:17 · 632 views
leetcode code 3232 : win digit game : python solutionleetcode blind 75 · 3:53 · 374 views
3232 Find if Digit Game Can Be WonCakot Coding · 3:44 · 279 views
3232. Find if Digit Game Can Be Won (Leetcode Easy)Programming Live with Larry · 2:54 · 258 views
Find if Digit Game Can Be Won | Leetcode weekly-contest-408Developer Coder · 2:23 · 179 views
Leetcode 3232 | Find if Digit Game Can Be Won | Java Solution with ExplanationCodeZen by Sharad · 5:44 · 170 views
3232. Find if Digit Game Can Be Won - using pythonLeetcode and Interview Question · 6:28 · 167 views
3232) Find if digit game can be won | Leetcode problem in ArraysCode Galaxy · 2:03 · 122 views
3232 Find if Digit Game Can Be Won (leetcode easy)Coder on A Farm · 2:07 · 108 views
The 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 <= 1001 <= nums[i] <= 99
Approach overview
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.
Approach 1: Sum Calculation Approach
In this approach, we iterate over the array to calculate the sum of single-digit numbers and double-digit numbers separately. Alice then selects either the sum of single-digit numbers or the sum of double-digit numbers, trying to maximize her advantage. We compare these sums with each other, and Bob's sum is the difference between the total sum and Alice's chosen sum. Alice wins if her chosen sum is greater than Bob's sum.
def canAliceWin(nums):
sum_single_digit = sum(num for num in nums if num < 10)
sum_double_digit = sum(num for num in nums if num >= 10)
total_sum = sum(nums)
alice_single_choice = sum_single_digit > (total_sum - sum_single_digit)
alice_double_choice = sum_double_digit > (total_sum - sum_double_digit)
return alice_single_choice or alice_double_choice
# Example Usage
print(canAliceWin([1,2,3,4,10])) # Output: False
print(canAliceWin([1,2,3,4,5,14])) # Output: True
print(canAliceWin([5,5,5,25])) # Output: Trueimport java.util.Arrays;
public class Main {
public static boolean canAliceWin(int[] nums) {
int sumSingleDigit = 0, sumDoubleDigit = 0;
for (int num : nums) {
if (num < 10) {
sumSingleDigit += num;
} else {
sumDoubleDigit += num;
}
}
int totalSum = Arrays.stream(nums).sum();
boolean aliceSingleChoice = sumSingleDigit > (totalSum - sumSingleDigit);
boolean aliceDoubleChoice = sumDoubleDigit > (totalSum - sumDoubleDigit);
return aliceSingleChoice || aliceDoubleChoice;
}
// Example Usage
public static void main(String[] args) {
System.out.println(canAliceWin(new int[]{1, 2, 3, 4, 10})); // Output: false
System.out.println(canAliceWin(new int[]{1, 2, 3, 4, 5, 14})); // Output: true
System.out.println(canAliceWin(new int[]{5, 5, 5, 25})); // Output: true
}
}#include <vector>
#include <numeric>
bool canAliceWin(const std::vector<int>& nums) {
int sum_single_digit = 0, sum_double_digit = 0;
for (int num : nums) {
if (num < 10) {
sum_single_digit += num;
} else if (num >= 10) {
sum_double_digit += num;
}
}
int total_sum = std::accumulate(nums.begin(), nums.end(), 0);
bool alice_single_choice = sum_single_digit > (total_sum - sum_single_digit);
bool alice_double_choice = sum_double_digit > (total_sum - sum_double_digit);
return alice_single_choice || alice_double_choice;
}
// Example Usage
// int main() {
// bool result1 = canAliceWin({1,2,3,4,10}); // Output: false
// bool result2 = canAliceWin({1,2,3,4,5,14}); // Output: true
// bool result3 = canAliceWin({5,5,5,25}); // Output: true
// }function canAliceWin(nums) {
let sumSingleDigit = 0, sumDoubleDigit = 0;
nums.forEach(num => {
if (num < 10) {
sumSingleDigit += num;
} else {
sumDoubleDigit += num;
}
});
const totalSum = nums.reduce((a, b) => a + b, 0);
const aliceSingleChoice = sumSingleDigit > (totalSum - sumSingleDigit);
const aliceDoubleChoice = sumDoubleDigit > (totalSum - sumDoubleDigit);
return aliceSingleChoice || aliceDoubleChoice;
}
// Example Usage
console.log(canAliceWin([1, 2, 3, 4, 10])); // Output: false
console.log(canAliceWin([1, 2, 3, 4, 5, 14])); // Output: true
console.log(canAliceWin([5, 5, 5, 25])); // Output: true#include <stdio.h>
#include <stdbool.h>
bool canAliceWin(int* nums, int numsSize) {
int sumSingleDigit = 0, sumDoubleDigit = 0, totalSum = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] < 10) {
sumSingleDigit += nums[i];
} else {
sumDoubleDigit += nums[i];
}
totalSum += nums[i];
}
bool aliceSingleChoice = sumSingleDigit > (totalSum - sumSingleDigit);
bool aliceDoubleChoice = sumDoubleDigit > (totalSum - sumDoubleDigit);
return aliceSingleChoice || aliceDoubleChoice;
}
// Example Usage
// int main() {
// int nums1[] = {1, 2, 3, 4, 10};
// printf("%d\n", canAliceWin(nums1, 5)); // Output: false
// int nums2[] = {1, 2, 3, 4, 5, 14};
// printf("%d\n", canAliceWin(nums2, 6)); // Output: true
// int nums3[] = {5, 5, 5, 25};
// printf("%d\n", canAliceWin(nums3, 4)); // Output: true
// }using System;
using System.Linq;
public class DigitGame {
public static bool CanAliceWin(int[] nums) {
int sumSingleDigit = 0, sumDoubleDigit = 0;
foreach (int num in nums) {
if (num < 10) {
sumSingleDigit += num;
} else {
sumDoubleDigit += num;
}
}
int totalSum = nums.Sum();
bool aliceSingleChoice = sumSingleDigit > (totalSum - sumSingleDigit);
bool aliceDoubleChoice = sumDoubleDigit > (totalSum - sumDoubleDigit);
return aliceSingleChoice || aliceDoubleChoice;
}
// Example Usage
public static void Main() {
Console.WriteLine(CanAliceWin(new int[] {1, 2, 3, 4, 10})); // Output: false
Console.WriteLine(CanAliceWin(new int[] {1, 2, 3, 4, 5, 14})); // Output: true
Console.WriteLine(CanAliceWin(new int[] {5, 5, 5, 25})); // Output: true
}
}This Python solution iterates over the list to sum up single- and double-digit numbers. It then checks both possible scenarios for Alice (choosing single or double digits) to see if her sum exceeds what Bob would get.
Time Complexity: O(n), where n is the number of elements in the array. This is because we iterate over the array to calculate sums.
Space Complexity: O(1), as we use a constant amount of space.
Approach 2: Categorize and Compare
This approach involves categorizing the numbers into single-digit and double-digit lists. We then calculate their sums and compare them against Bob's sum of the remaining numbers to see if Alice can win with any of these groupings.
def canAliceWin(nums):
single_digit_sum = sum(x for x in nums if x <= 9)
double_digit_sum = sum(x for x in nums if x >= 10)
total_sum = sum(nums)
return single_digit_sum > (total_sum - single_digit_sum) or double_digit_sum > (total_sum - double_digit_sum)
# Example Usage
print(canAliceWin([1, 2, 3, 4, 10])) # Output: False
print(canAliceWin([1, 2, 3, 4, 5, 14])) # Output: True
print(canAliceWin([5, 5, 5, 25])) # Output: Truepublic class DigitGame {
public static boolean canAliceWin(int[] nums) {
int singleDigitSum = 0, doubleDigitSum = 0;
int totalSum = 0;
for (int num : nums) {
if (num < 10) singleDigitSum += num;
else doubleDigitSum += num;
totalSum += num;
}
return singleDigitSum > (totalSum - singleDigitSum)
|| doubleDigitSum > (totalSum - doubleDigitSum);
}
// Example Usage
public static void main(String[] args) {
System.out.println(canAliceWin(new int[]{1, 2, 3, 4, 10})); // Output: false
System.out.println(canAliceWin(new int[]{1, 2, 3, 4, 5, 14})); // Output: true
System.out.println(canAliceWin(new int[]{5, 5, 5, 25})); // Output: true
}
}#include <vector>
bool canAliceWin(const std::vector<int>& nums) {
int single_digit_sum = 0, double_digit_sum = 0;
int total_sum = 0;
for (int num : nums) {
if (num < 10) single_digit_sum += num;
else double_digit_sum += num;
total_sum += num;
}
return single_digit_sum > (total_sum - single_digit_sum) ||
double_digit_sum > (total_sum - double_digit_sum);
}
// Example Usage
// int main() {
// printf("%d\n", canAliceWin({1, 2, 3, 4, 10})); // Output: false
// printf("%d\n", canAliceWin({1, 2, 3, 4, 5, 14})); // Output: true
// printf("%d\n", canAliceWin({5, 5, 5, 25})); // Output: true
// }function canAliceWin(nums) {
let singleDigitSum = 0, doubleDigitSum = 0;
let totalSum = 0;
for (let num of nums) {
if (num < 10) singleDigitSum += num;
else doubleDigitSum += num;
totalSum += num;
}
return singleDigitSum > (totalSum - singleDigitSum)
|| doubleDigitSum > (totalSum - doubleDigitSum);
}
// Example Usage
console.log(canAliceWin([1, 2, 3, 4, 10])); // Output: false
console.log(canAliceWin([1, 2, 3, 4, 5, 14])); // Output: true
console.log(canAliceWin([5, 5, 5, 25])); // Output: true#include <stdbool.h>
bool canAliceWin(int* nums, int numsSize) {
int singleDigitSum = 0, doubleDigitSum = 0;
int totalSum = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] < 10) {
singleDigitSum += nums[i];
} else {
doubleDigitSum += nums[i];
}
totalSum += nums[i];
}
return singleDigitSum > (totalSum - singleDigitSum)
|| doubleDigitSum > (totalSum - doubleDigitSum);
}
// Example Usage
// int main() {
// int nums1[] = {1,2,3,4,10};
// printf("%d\n", canAliceWin(nums1, 5)); // Output: false
// int nums2[] = {1,2,3,4,5,14};
// printf("%d\n", canAliceWin(nums2, 6)); // Output: true
// int nums3[] = {5,5,5,25};
// printf("%d\n", canAliceWin(nums3, 4)); // Output: true
// }using System;
public class DigitGame {
public static bool CanAliceWin(int[] nums) {
int singleDigitSum = 0, doubleDigitSum = 0;
int totalSum = 0;
foreach (int num in nums) {
if (num < 10) singleDigitSum += num;
else doubleDigitSum += num;
totalSum += num;
}
return singleDigitSum > (totalSum - singleDigitSum)
|| doubleDigitSum > (totalSum - doubleDigitSum);
}
// Example Usage
public static void Main() {
Console.WriteLine(CanAliceWin(new int[] {1, 2, 3, 4, 10})); // Output: false
Console.WriteLine(CanAliceWin(new int[] {1, 2, 3, 4, 5, 14})); // Output: true
Console.WriteLine(CanAliceWin(new int[] {5, 5, 5, 25})); // Output: true
}
}This Python code checks whether the sum of single-digit or double-digit numbers is greater than the sum of the remaining numbers. This determines if Alice can win.
Time Complexity: O(n). We perform summation over the array.
Space Complexity: O(1). Only a few integer variables are used.
Approach 3: Summation
According to the problem description, as long as the sum of the units digits is not equal to the sum of the tens digits, Alice can always choose a larger sum to win.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function canAliceWin(nums: number[]): boolean {
let [a, b] = [0, 0];
for (const x of nums) {
if (x < 10) {
a += x;
} else {
b += x;
}
}
return a !== b;
}func canAliceWin(nums []int) bool {
a, b := 0, 0
for _, x := range nums {
if x < 10 {
a += x
} else {
b += x
}
}
return a != b
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sum Calculation Approach | Time Complexity: O(n), where n is the number of elements in the array. This is because we iterate over the array to calculate sums. |
| Categorize and Compare | Time Complexity: O(n). We perform summation over the array. |
| Summation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sum Calculation Approach | O(n) | O(1) | Best general solution; single pass computing sums of one-digit and two-digit numbers. |
| Categorize and Compare | O(n) | O(1) | Useful when explicitly grouping numbers by digit length before comparing totals. |
Frequently asked questions
Is Find if Digit Game Can Be Won easy or hard?
Find if Digit Game Can Be Won is categorized as an Easy problem. The core idea is recognizing that Alice wins whenever the sum of one-digit numbers and two-digit numbers are not equal, which can be checked with a single array pass.
Find if Digit Game Can Be Won Python/Java solution
The implementation in Python or Java follows the same pattern: loop through the array, add numbers less than 10 to one sum and the rest to another, then return whether the two sums differ. The logic is identical across languages and runs in O(n) time.
How to solve Find if Digit Game Can Be Won in O(n)?
Iterate through the array and maintain two variables: one for the sum of numbers less than 10 and another for numbers greater than or equal to 10. After the loop, compare the two sums. If they are different, Alice selects the larger group and wins.
What is the best approach for Find if Digit Game Can Be Won?
The best approach is to compute the sum of one-digit numbers and the sum of two-digit numbers in a single pass through the array. Alice can win if the two sums are not equal because she can choose the category with the larger total. This solution runs in O(n) time with O(1) space.
Is Find if Digit Game Can Be Won asked at Google/Amazon/Meta?
Problems of this style appear frequently in interviews at companies like Amazon and Google because they test basic array traversal and logical reasoning. The difficulty is Easy, but interviewers often use it to evaluate clarity of thought and edge-case handling.
What data structure is used in Find if Digit Game Can Be Won?
The problem primarily uses a simple array traversal. No advanced data structures are required—only a few integer variables to track category sums during iteration.
What is the time complexity of Find if Digit Game Can Be Won?
The optimal solution runs in O(n) time because you scan the array once to compute two sums. Only a few integer variables are used, so the space complexity remains O(1).