NewGuy - 1 year ago 87

Python Question

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`

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 Source

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

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.

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