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).