We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find if Digit Game Can Be Won

Number: 3515

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of positive integers, Alice and Bob play a game where Alice can choose either all single-digit numbers or all double-digit numbers. The rest of the numbers go to Bob. Alice wins if the sum of her chosen numbers is strictly greater than the sum of Bob's numbers. Return true if Alice can win the game by picking one of the two groups; otherwise, return false.

Key Insights

  • Separate the numbers into two groups: single-digit numbers (1-9) and double-digit numbers (10-99).
  • There are exactly two scenarios:
    1. Alice picks all single-digit numbers and Bob gets all double-digit numbers.
    2. Alice picks all double-digit numbers and Bob gets all single-digit numbers.
  • Compute the sum for each group and compare according to the game rule.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(1), using only a fixed number of extra variables.

Solution

The solution involves iterating through the array once to compute the sum of single-digit numbers and the sum of double-digit numbers. Then, evaluate the two possible scenarios:

  1. If the sum of single-digit numbers is strictly greater than the sum of double-digit numbers.
  2. If the sum of double-digit numbers is strictly greater than the sum of single-digit numbers. If either condition is met, Alice can win the game. This method uses simple arithmetic and constant extra space.

Code Solutions

# Python solution with detailed comments
def winDigitGame(nums):
    # Initialize sums for one-digit and two-digit numbers
    single_digit_sum = 0
    double_digit_sum = 0
    
    # Iterate over each number in the list
    for num in nums:
        # Check if number is a single-digit number (1 to 9)
        if 1 <= num <= 9:
            single_digit_sum += num
        else:  # Number is a double-digit number (10 to 99)
            double_digit_sum += num
    
    # Check two scenarios:
    # 1. Alice picks single-digit numbers
    scenario1 = single_digit_sum > double_digit_sum
    # 2. Alice picks double-digit numbers
    scenario2 = double_digit_sum > single_digit_sum
    
    # Return true if either scenario allows Alice to win
    return scenario1 or scenario2

# Example usage:
print(winDigitGame([1,2,3,4,10]))    # Output: False
print(winDigitGame([1,2,3,4,5,14]))    # Output: True
print(winDigitGame([5,5,5,25]))        # Output: True
← Back to All Questions