algoadvance

[LeetCode 3232: Find if Digit Game Can Be Won-out]

You are given a string s containing digits from ‘1’ to ‘9’. In each move, you can pick one digit from the string and remove it. If the sum of the remaining string’s digits is divisible by 3, you win the game. Return True if you can win the game and False otherwise.

Example

1. Input: s = "123" Output: True Explanation: By removing ‘1’, the sum of “23” is 5, and 5 is not divisible by 3. By removing ‘2’, the sum of “13” is 4, and 4 is not divisible by 3. By removing ‘3’, the sum of “12” is 3, which is divisible by 3. So you can win the game.

2. Input: s = "111" Output: False Explanation: No matter which digit you remove, the sum of the remaining digits will be divisible by 3.

Clarifying Questions

1. What is the length of the string s?
   • The length of the string can be up to 10^5.
2. Is the string guaranteed to only contain digits from ‘1’ to ‘9’?
   • Yes, the string s contains only digits from ‘1’ to ‘9’.
3. Is it possible that the given string s already satisfies the condition (i.e., the sum of its digits is divisible by 3)?
   • Yes, and it should be considered that removing any one digit might impact whether the sum remains divisible by 3 or not.

Strategy

1. Calculate the sum of the digits of the string s.
2. Check if the sum is already divisible by 3:
   • If it is, removing any digit would typically make the sum non-divisible except very specific cases, so we assume this doesn’t mean the initial win state uniquely determines subsequent losses without check.
3. Iterate through each digit in the string s:
   • Temporarily remove the digit and calculate the sum of the remaining digits.
   • Check if the new sum is divisible by 3.
   • If it is, return True.
4. If no single digit removal results in a sum divisible by 3, return False.

Code

def can_win_digit_game(s: str) -> bool:
    # Calculate the sum of the digits
    total_sum = sum(map(int, s))
    
    # Check if we can remove one digit to make the sum of the remaining digits divisible by 3
    for char in s:
        digit = int(char)
        new_sum = total_sum - digit
        
        if new_sum % 3 == 0:
            return True
    
    return False

# Example test cases
print(can_win_digit_game("123"))  # Should return True
print(can_win_digit_game("111"))  # Should return False

Time Complexity

• Time Complexity: O(n) where ( n ) is the length of the string ( s ). We iterate through the string a constant number of times (once to compute the sum and once to check each removal).
• Space Complexity: O(1) as we only use a fixed amount of extra space.

With this approach, we ensure that the function efficiently determines if it’s possible to win the game by removing a single digit such that the remaining sum is divisible by 3.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?