Skip to main content
Handle the case of digits = [ ]
Source Link
RootTwo
  • 10.2k
  • 1
  • 13
  • 30
from collections import Counter

def make_number(digits: [int]) -> int:
    result = 0
    
    for digit in digits:
        result = 10*result + digit
    
    return result


def solution(digits: [int]) -> int:
    """Returns the largest number that that is divisible by 3 that can be made
       from the digits. Returns 0 if it is not possible to make a number 
       divisible by 3. (That is somewhat ambiguous, because 0 is divisible
       by 3, you can't determine whether 0 means failure,
       or there was a 0 in digits).
    """ 

    if not digits:
        return 0
    
    # Prepopulate keys in the counter in descending order.
    count = Counter(dict.fromkeys(range(9,-1,-1), 0))
    count.update(digits)
    
    remainder = sum(digits) % 3
        
    if remainder == 0:
        return make_number(count.elements())
    
    # One group is [1, 4, 7] and the other is [2, 5, 8].
    # Which is which depends on remainder.
    remainder_group = range(remainder, 10, 3)
    other_group = range(3 - remainder, 10, 3)

    # If possible, remove a single digit, where digit % 3 == remainder.
    # The `groups` are in ascending order so small digits are removed before 
    # large ones.
    # If 'any()' is True, 'index' will be the digit that cause it to succeed.
    if any(count[(index:=digit)] for digit in remainder_group):
        count[index] -= 1
        return make_number(count.elements())

    # Otherwise, remove 2 digits from the other group
    if any(count[(index:=digit)] for digit in other_group):
        count[index] -= 1

        if any(count[(index:=digit)] for digit in other_group):
            count[index] -= 1
            return make_number(count.elements())

    return 0
from collections import Counter

def make_number(digits: [int]) -> int:
    result = 0
    
    for digit in digits:
        result = 10*result + digit
    
    return result


def solution(digits: [int]) -> int:
    """Returns the largest number that that is divisible by 3 that can be made
       from the digits. Returns 0 if it is not possible to make a number 
       divisible by 3. (That is somewhat ambiguous, because 0 is divisible
       by 3, you can't determine whether 0 means failure,
       or there was a 0 in digits).
    """
    
    # Prepopulate keys in the counter in descending order.
    count = Counter(dict.fromkeys(range(9,-1,-1), 0))
    count.update(digits)
    
    remainder = sum(digits) % 3
        
    if remainder == 0:
        return make_number(count.elements())
    
    # One group is [1, 4, 7] and the other is [2, 5, 8].
    # Which is which depends on remainder.
    remainder_group = range(remainder, 10, 3)
    other_group = range(3 - remainder, 10, 3)

    # If possible, remove a single digit, where digit % 3 == remainder.
    # The `groups` are in ascending order so small digits are removed before 
    # large ones.
    # If 'any()' is True, 'index' will be the digit that cause it to succeed.
    if any(count[(index:=digit)] for digit in remainder_group):
        count[index] -= 1
        return make_number(count.elements())

    # Otherwise, remove 2 digits from the other group
    if any(count[(index:=digit)] for digit in other_group):
        count[index] -= 1

        if any(count[(index:=digit)] for digit in other_group):
            count[index] -= 1
            return make_number(count.elements())

    return 0
from collections import Counter

def make_number(digits: [int]) -> int:
    result = 0
    
    for digit in digits:
        result = 10*result + digit
    
    return result


def solution(digits: [int]) -> int:
    """Returns the largest number that that is divisible by 3 that can be made
       from the digits. Returns 0 if it is not possible to make a number 
       divisible by 3. (That is somewhat ambiguous, because 0 is divisible
       by 3, you can't determine whether 0 means failure,
       or there was a 0 in digits).
    """ 

    if not digits:
        return 0
    
    # Prepopulate keys in the counter in descending order.
    count = Counter(dict.fromkeys(range(9,-1,-1), 0))
    count.update(digits)
    
    remainder = sum(digits) % 3
        
    if remainder == 0:
        return make_number(count.elements())
    
    # One group is [1, 4, 7] and the other is [2, 5, 8].
    # Which is which depends on remainder.
    remainder_group = range(remainder, 10, 3)
    other_group = range(3 - remainder, 10, 3)

    # If possible, remove a single digit, where digit % 3 == remainder.
    # The `groups` are in ascending order so small digits are removed before 
    # large ones.
    # If 'any()' is True, 'index' will be the digit that cause it to succeed.
    if any(count[(index:=digit)] for digit in remainder_group):
        count[index] -= 1
        return make_number(count.elements())

    # Otherwise, remove 2 digits from the other group
    if any(count[(index:=digit)] for digit in other_group):
        count[index] -= 1

        if any(count[(index:=digit)] for digit in other_group):
            count[index] -= 1
            return make_number(count.elements())

    return 0
Source Link
RootTwo
  • 10.2k
  • 1
  • 13
  • 30

The original solution and the proposed solutions include a step of sorting the list of digits. So technically, they are O(n log n), but the list is at most 9 digits long, so the difference may not be noticeable unless the code is being run many (millions?) of times.

Nevertheless, here is an O(n) version:

from collections import Counter

def make_number(digits: [int]) -> int:
    result = 0
    
    for digit in digits:
        result = 10*result + digit
    
    return result


def solution(digits: [int]) -> int:
    """Returns the largest number that that is divisible by 3 that can be made
       from the digits. Returns 0 if it is not possible to make a number 
       divisible by 3. (That is somewhat ambiguous, because 0 is divisible
       by 3, you can't determine whether 0 means failure,
       or there was a 0 in digits).
    """
    
    # Prepopulate keys in the counter in descending order.
    count = Counter(dict.fromkeys(range(9,-1,-1), 0))
    count.update(digits)
    
    remainder = sum(digits) % 3
        
    if remainder == 0:
        return make_number(count.elements())
    
    # One group is [1, 4, 7] and the other is [2, 5, 8].
    # Which is which depends on remainder.
    remainder_group = range(remainder, 10, 3)
    other_group = range(3 - remainder, 10, 3)

    # If possible, remove a single digit, where digit % 3 == remainder.
    # The `groups` are in ascending order so small digits are removed before 
    # large ones.
    # If 'any()' is True, 'index' will be the digit that cause it to succeed.
    if any(count[(index:=digit)] for digit in remainder_group):
        count[index] -= 1
        return make_number(count.elements())

    # Otherwise, remove 2 digits from the other group
    if any(count[(index:=digit)] for digit in other_group):
        count[index] -= 1

        if any(count[(index:=digit)] for digit in other_group):
            count[index] -= 1
            return make_number(count.elements())

    return 0

Each of count.update(), sum() and make_number() are O(n). Everything else is O(1) (i.e., constant time).