NewGuy NewGuy - 1 month ago 25
Python Question

Reduce runtime when finding permutations

I am working on one of Google's FooBar challenges for fun and running into a Time Limit Exceeded error when executing it in Google's run time environment. My solution runs fine - and to my eyes quickly - in my local development environment.

This is my code:

from itertools import permutations

def answer(l):
options = []
for r in range(1, len(l) + 1):
for p in permutations(l, r=r):
n = int(''.join(map(str, p)))
if n % 3 == 0:
options.append(n)
numbers = sorted(options, reverse=True)
return numbers[0]

l = [3, 1, 4, 1, 5, 9]
#l = [3, 1, 4, 1]
print(answer(l))


The goal is to find the largest number that is divisible by 3 from the list of numbers that is passed in.

The output of the two examples should be:

[3, 1, 4, 1, 5, 9] => 94311
[3, 1, 4, 1] => 4311


Based on the comments to generate the permutations from largest to smallest (instead of smallest to largest) and then breakout, I've modified the code. Against, it works in the local environment but the Google runtime says that the timelimit has been exceeded:

def answer(l):
options = []
l = sorted(l, reverse=True)
for r in range(len(l) + 1, 1, -1):
for p in permutations(l, r=r):
n = int(''.join(map(str, p)))
if n % 3 == 0:
return n
return 0


I am sorting the input list based on the
permutations
docs
that say the tuples will be sorted if the input is sorted. It then, since it should be sorted, the first time it finds a value divisible by 3, that will be the higest value

As I said, my code (both versions) works. But, I seem to be running longer than Google expects. How can I reduce the run time of the above code?

Answer
  1. The highest number will have the most number of digits. So for a list of size n, the search should start from n and continue to n-1, n-2...

  2. The numbers divisible by 3 will always be in the solution. For example 2514 is divisible by 3 so is 32514 or 35314. Therefore you can reduce the search to the digits that are not divisible by 3.

  3. For a list of n digits that are not divisible by 3 (n>=3), you can get a number divisible by 3 by removing at most 2 digits. This is because the summation will have the remainder 1 or 2. If it is 1, in the worst case you can remove 2 digits with a remainder of 2. If it is 2, again in the worst case you can remove 2 digits with a remainder of 1.

Now the algorithm:

You have a list of numbers:

divisible = [i for i in numbers if i % 3 == 0]
candidate_list = [i for i in numbers if i % 3 != 0]

If the summation of candidate_list is divisible by 3, then you have the answer. If not, look at the remainder:

remainder = sum(candidate_list) % 3

If the remainder is 1, we are going to search for 1, 4, or 7 in the candidate list. If it is 2, the numbers will be 2, 5, and 8. If we find a number, we are going to remove that from the list and the sum of the remaining digits will be divisible by three.

if remainder!=0:
    for i in range(3):
        if (remainder + i*3) in candidate_list:
            candidate_list.remove(remainder + i*3)
            return candidate_list

This will start the search from the smallest digit and break out of the loop when a digit is found. If not, we will search for two digits instead of 1.

counter = 0
for candidate in candidate_list:
    if candidate % 3 + remainder == 3:
        candidate_list.remove(candidate)
        counter += 1
        if counter > 1:
            return candidate_list

Overall, you'll have something like this:

numbers = [3, 1, 4, 1, 5, 9, 0, 2, 4, 7, 9, 1, 3]
divisible = [i for i in numbers if i % 3 == 0]

def search(numbers):
    candidate_list = sorted([i for i in numbers if i % 3 != 0])
    remainder = sum(candidate_list) % 3
    if remainder!=0:
        for i in range(3):
            if (remainder + i*3) in candidate_list:
                candidate_list.remove(remainder + i*3)
                return candidate_list
        counter = 0
        for candidate in candidate_list:
            if candidate % 3 + remainder == 3:
                candidate_list.remove(candidate)
                counter += 1
                if counter > 1:
                    return candidate_list
    else return candidate_list

candidate_list = search(numbers)
fin = int(''.join(map(str, sorted(divisible + candidate_list, reverse=True))))