Teaching Kids Programming – Find if Digit Game Can Be Won

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Find if Digit Game Can Be Won

As long as the two sums (1 single digit, and 2 single digits) are not the same, Alice will win, so we can iterate the array twice to compute the sums for each cases. The time complexity is O(N), where N is the number of the elements in the array. The space complexity is O(1) constant.

1
2
3
4
5

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        s1 = sum([x for x in nums if x < 10])
        s2 = sum([x for x in nums if x >= 10])
        return s1 != s2

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        s1 = sum([x for x in nums if x < 10])
        s2 = sum([x for x in nums if x >= 10])
        return s1 != s2

A slightly improved version would be to iterate the array once, when the number is 1 digit, we increment the counter, otherwise, we decrement respectively. At the end, when the counter is zero, it means both sums are equal, otherwise, the sums are not equal.

1
2
3
4
5
6
7
8
9

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        s = 0
        for i in nums:
            if i < 10:
                s += i
            else:
                s -= i
        return s != 0

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        s = 0
        for i in nums:
            if i < 10:
                s += i
            else:
                s -= i
        return s != 0

The same time complexity O(N) and O(1) space. But this approach runs faster because only one pass is required.

–EOF (The Ultimate Computing & Technology Blog) —