Google Foobar - Please Pass the Coded Messages

This week I got around to closing out Level 2 Part 2 of the Google Foobar Challenge - "Please Pass the Coded Messages"

Given a list of digits, our job is to find the order of those digits that yields the maximum number that is divisible by 3.

So a list like [3, 1, 4, 1, 5, 9] would yield 94311, and the list [3, 1, 4, 1] gives us 4311. 

Here’s something to keep in mind that will make our job easier: a number is divisible by 3 if and only if the sum of its digits is also divisible by 3. 

So we could have the following numbers: 375, 753, 357, and 735, and they’d all be divisible by 3, because the sum of their digits is divisible by 3.

If we were to rearrange the digits in the number ‘892’, they will never be divisible by 3, because the sum of their digits will always be 19, and 19 isn’t divisible by 3. We’re left with a non zero remainder each time:

298 / 3 = 99.33333333

829 / 3 = 276.3333333

289 / 3 = 96.33333333

892 / 3 = 297.3333333

This helps a lot. We just need to sort the list once in descending order: so [3, 1, 4, 1, 5, 9] becomes [9, 5, 4, 3, 1, 1], and then we just need to determine the digits to exclude from this sequence while still making it divisible by 3.

Let’s try with our first sequence of digits: [3, 1, 4, 1, 5, 9].

We’ll sort in descending order to yield: [9, 5, 4, 3, 1, 1]. Stringing these digits together we get 954311.

In this case, 954311 is not divisible by 3, so let’s try removing 4 from that series to get us the next largest number: 95311.

Well, 95311 is also not divisible by 3, so let’s take the 5 out and this time try with the same number of digits but keeping the 4 in there: 94311. 94311 is divisible by 3 (since 94311 / 3 = 31437) and so we stop. The answer is 94311.

The next list is easier: [3, 1, 4, 1]. After sorting we get 4311, and 4311 is divisible by 3 (4311 / 3 = 1437), so we end right there.

Pay attention to this tidbit in the instructions : “L will contain anywhere from 1 to 9 digits.”  We’re only going to be given short sequences to work with. Therefore, we can exploit bit masking to represent the combinations of digits that we’ll include/exclude from our number. 

We can start with a bit mask of 1 shifted left by the length of the list (6 in the case of [9, 5, 4, 3, 1, 1]) which yields the binary value 1000000 (or 64 in decimal). We then start counting backwards starting from mask - 1 (63 in decimal or 111111). For each bit position, 1 means we’ll include the digit from that position in the list, and 0 means we don’t include it:

111111 means we include all digits — which would be 954311. 

111110 would be every digit except the last one: 95431.

101010 would yield: 941.

If a combination is divisible by 3 and it’s the max number we’ve encountered, we’ll record it as the max value we have so far. We’ll return whatever that value is at the end. Sometimes it won’t be possible to create any number that is divisible by 3 from a sequence of digits, and in those cases we return 0.

Here’s my full answer in python, which passed all the test cases:

def solution(l):

    lLen = len(l)

    max = 1 << lLen

    l.sort(reverse=True)

    maxAttempt = 0

    for mask in reversed(range(max)):

        attempt = ""

        for index in range(mask.bit_length()):

            attempt += str(l[index]) if (mask >> index) & 1 == 1 else ''

        if attempt == '':

            attempt = 0

        attempt = int(attempt)

        if attempt % 3 == 0:

            if attempt > maxAttempt:

                maxAttempt = attempt

    return maxAttempt

And with that, it’s time to move on to level 3!