Given a list of digits, construct the largest number divisible by 3

Question

What is the performance of this program? What should I do differently to optimize performance (O(n))? How would you grade it relative to what defines an optimal, elegantly-written program?

Input: A list l that has a length between 1 and 9 elements, consisting of the numbers from 0-9. The length of l and the values of the elements are both random. Output: The largest number that can be constructed from the list that is divisible by 3. If not possible, return(0).

Test Case: input: l = [3,1,4,1,5,9] output: 94311

def solution(l):
    sum = 0
    
    # Sum the elements of l
    for elem in l:
        sum += elem
        
    # Determine whether l contains a number divisible 
    # by 3, using the modulo operator. If sum modulo
    # 3 is equivalent to 1 or 2, we split the elements
    # into two separate lists, q1 and q2.
    if (sum < 3):
        return(0)
    elif (sum % 3 == 0):
        l.sort(reverse=True)
        x = ''
        for i in l:
            x = x + str(i)
        return(int(x))
    else:
        q1 = [x for x in l if x % 3 == 1]
        q1.sort(reverse=False)
        q2 = [x for x in l if x % 3 == 2]
        q2.sort(reverse=False)
        l = [x for x in l if x % 3 == 0]
    
    # Remove proper elements such that the
    # sum of l is divisible by 3.
    if (sum % 3 == 1):
        if (len(q1) != 0):
            q1.pop(0)
        elif (len(q2) >= 2):
            q2.pop(0)
            q2.pop(0)
    elif (sum % 3 == 2):
        if (len(q2) != 0):
            q2.pop(0)
        elif (len(q1) >= 2):
            q1.pop(0)
            q1.pop(0)
    
    # Assemble largest number in l divisible
    # by 3 by extending l to q1 and q2.
    l.extend(q1)
    l.extend(q2)
    l.sort(reverse=True)
    
    # Recheck sum of l and test for
    # divisbility. If divisible by 3
    # concatenate the elements of l into x.
    sum2 = 0
    if (len(l) > 0):
        for elem in l:
            sum2 += elem
        if (sum2 % 3 == 0):
            x = ''
            for i in l:
                x = x + str(i)
            return(int(x))
        else:
            return(0)
    else:
        return(0)

Answer 1

Generally, (design,) program and code the way you think about the problem.
(This may change, as may requirements: Make oncoming change easy, if not safe.
This includes avoiding duplicate code - handling non-zero remainders, computing the result from the digits.)
(And leave worrying about performance to when there is an indication this is (promising to be) a problem. 1 to 9 elements? No problem if what's waiting is human.)

Don't write, never publish uncommented/undocumented code.
Python got it right specifying docstrings such that it is easy to copy them with the code, and tedious to copy the code without them.

The are many angles to view the problem at hand - leveraging collection.Counter:
(one rubber point for spotting deviations from the Style Guide)

from collections import Counter

def biggest_multiple_of_3(digits, base=10):
    """ Return the biggest multiple of 3 possible by 
        rearranging some of the digits (0 if impossible). 
        (works for base 3b+1 for any non-negative b.)
    """
    if not digits:
        return 0
    # approach: leave unused 1. fewest 2. smallest digits as needed
    ascending = sorted(int(d) for d in digits)  # int(d, base) mandates d string
    counts = Counter(d % 3 for d in ascending)
    remainder = (counts[1] + 2*counts[2]) % 3
    if 0 == remainder:
        rid, count = 3, 0
    elif 0 < counts[remainder]:
        rid, count = remainder, 1
    elif 1 < counts[3 - remainder]:
        rid, count = 3 - remainder, 2
    else:
        return 0
    if len(digits) <= count:  # entirely redundant
        return 0
    power = 1
    multiple = 0
    for d in ascending:
        # print(power, d, rid, count)
        if 0 < count and d%3 == rid:
            count -= 1
        else:
            multiple += d*power
            power *= base
    return multiple

def solution(l):              # don't let interface requirements ruin your code
    biggest_multiple_of_3(l)


if __name__ == '__main__':
    biggest_multiple_of_3('314159')

Answer 2

I have made the following changes to my code. This version seems to be less chaotic, has better structure, more pythonic code, and more efficient use of each word of code.

def solution(l):
    # Declare variables
    sum1 = sum(l)
    rem = sum1 % 3
    
    # Check value of remainder using modulo
    if rem > 0:
        q1 = sorted([x for x in l if x % 3 == 1])
        q2 = sorted([x for x in l if x % 3 == 2])

        # Depending on the remainder, remove the elements that
        # will produce the largest number divisible by 3.
        if rem == 1 and len(q1) != 0:
            l.remove(q1[0])
        elif len(q2) >= 2:
            l.remove(q2[0])
            l.remove(q2[1])
        elif rem == 2 and len(q2) != 0:
            l.remove(q2[0])
        elif len(q1) >= 2:
            l.remove(q1[0])
            l.remove(q1[1])
            
        # If l is empty, sort l into descending order.
        # If l is not empty, convert l to string.
        if len(l) != 0:
            l.sort(reverse=True)
            x = ''
            for i in l: 
                x = x + str(i)  
        else:
            return(0)
    # If rem == 0, sort l into descending
    # order, and convert l to a string.
    elif rem == 0:
        l.sort(reverse=True)
        x = ''
        for i in l: 
            x = x + str(i)
    # Convert x and return an integer.  
    return(int(x))

Answer 3

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

    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

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