Counting numbers that are divisible by 3 and can be produced from the digits of a given number

Question

I'm trying to solve this problem from codewars.

Problem

Given a certain number, how many multiples of three could you obtain with its digits? Suppose that you have the number 362. The numbers that can be generated from it are: 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632 and among those 3, 6, 36, 63 are divisible by 3.

We need a function that can receive a number ann may output in the following order:

• the amount of multiples(without 0)

• the maximum multiple

My solution

I have found all possible permutations of the digits of the given number and checked if the number is divisible by 3. Here is my code -

from itertools import permutations as perm
from functools import reduce

def to_int(digs):    # takes a list of digits of an integer and returns the number 
    n = reduce(lambda total, d: 10 * total + d, digs, 0)
    return n

def find_mult_3(num):
    digs = list(map(int, str(num)))
    perms = []        # stores all possible permutations with the digits of num
    for i in range(1, len(digs)+1):
        perms.extend(list(p) for p in set(perm(digs, i)))

    count, mx = 0, 0
    seen = set()      # to keep track of divisors already seen
    if 0 in perms:
        perms.remove(0)
    for p in perms:
        n = to_int(p)
        if n % 3 == 0 and n not in seen:
            if mx < n:
                mx = n
            count += 1
            seen.add(n)

    return [count, mx]

But getting TLE, is there any way to make this program faster or any other clever way to solve this problem? Please ask if there is any need for clarification in any part of the code.

Answer 1

The algorithm can be improved, so that we do less work:

Use the fact that multiples of 3 have a sum of digits that's also a multiple of 3. That means we can select all the distinct combinations of digits, and discard any that don't sum to a multiple of 3. Only for those sets not discarded, we can compute the number of permutation of the selected digits. (Note that we don't have to actually produce all the numbers, merely count them - so if we have n different digits, we count n! permutations; if p of them are identical, then n!/p!, and so on).

For example, with input 5532:

• 5+5+3+2 is 15, this gives us 4!/2! permutations that are multiples of 3 (and remember 5532 as the largest such multiple).
• 5+5+3 is 13, so ignore it.
• 5+5+2 is 12, giving us 3!/2! more permutations to add to our count.
• 5+3+2 is 10; ignore it.
• 5+5 is 10; ignore it.
• 5+3 is 8; ignore it.
• 5+2 is 7; ignore it.
• 2+3 is 5; ignore it.
• 5 alone - ignore
• 3 alone - add one to the count.
• 2 alone - ignore.

And we're done; the total count is 4!/2! + 3!/2! + 1 = 16.

Answer 2

From the mathematical point , one number is divisible by 3 if sum of its digits is divisible by 3 and it is valid the commutative property, so 3 + 6 + 2 is equal to 6 + 3 + 2 because you can commute elements in every position and still obtain the same result. So if sum of n digits is divisible by 3, the n! permutations of the number including itself are still divisible by 3. Below the execution of algorithm starting from number 362:

1. First step: you start from number 362 and the sum is 11 that is not divisible by 3 and so are the commutation of its digits that are the permutation of the number: the amount of multiples is 0 and the maximum multiple is None.
2. Second step: you subtract one digit from number '362' obtaining numbers 62, 32, 36; now there is one number 36 that is divisible by 3 and its permutations are divisible by 3. In this case there is the permutation 63 that is the maximum multiple. The amount of multiples is now 2.
3. Third step: you subtract one digit from number 36 obtaining numbers 3 and 6: both are divisible by 3 and the final amount of multiples is now 4.

Answer 3

Variable names

The few keystrokes you save by not having to type digits or permutations in full is not worth it. Just name em digits and permutations. For the import, just import itertools instead of from itertools import permutations as perm

to_int

To take a sum, reduce is seldom needed. You can explain this logic simpler like :

def to_int(digits): return sum(x * 10 ** i for i, x in enumerate(reversed(digits)))

itertools chain

instead of having a list and extending it,

perms = []        # stores all possible permutations with the digits of num
for i in range(1, len(digs)+1):
    perms.extend(list(p) for p in set(perm(digs, i)))

you can use:

permutations = list(
    itertools.chain.from_iterable(
        set(itertools.permutations(digs, i)) for i in range(1, len(digs) + 1)
    )
)

Even better would be to filter as soon as possible, and use:

permutations = itertools.chain.from_iterable(
    set(
        permutation
        for permutation in itertools.permutations(digits, i)
        if (
            sum(permutation)
            and sum(permutation) % 3 == 0
            and permutation[0] != 0
        )
    )
    for i in range(1, len(digits) + 1)
)

You don't even need to instantiate the list. The sum(permutation) test checks for a permutation with only 0s. Then the rest becomes a simple:

count = 0
running_max = 0
for permutation in permutations:
    n = to_int(permutation)
    count += 1
    running_max = max(running_max, n)
return count, running_max

But it turns out you don't need all the permutations on a list

not needed operations

Not all operations need to be done on all numbers:

For a given combination of digits:

• if its sum is not divisible by 3, it can be discarded
• it has 1 maximum permutation, which can be easily calculated by sum(x * 10 ** i for i, x in enumerate(sorted(combination))), so to_int is no longer needed
• if there are no 0s in it, the number of permutations can be calculated with this formula
• if there are 0s the simplest will be to generate all the combinations not starting with 0 and counting them:

In python, I would do this like this:

import itertools
from collections import Counter
from math import factorial


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(
        itertools.combinations(s, r) for r in range(len(s) + 1)
    )

This itertools recipe gives all of the combinations for all of the subsets

def product(iterable):
    result = 1
    for i in iterable:
        result *=  i
    return result

helper method to calculate the product of an iterable

def permutation_count(combination):
    total = sum(combination)
    if total == 0: # all digits are 0
        return 0
    if 0 not in combination:
        counter = Counter(combination)
        return int(
            factorial(total) / product(factorial(i) for i in counter.values())
        )

    return len(
        {
            permutation
            for permutation in itertools.permutations(combination)
            if permutation[0] != 0
        }
    )

def multiples(number):
    digits = map(int, str(number))
    running_count = 0
    running_max = 0
    for combination in powerset(digits):
        if sum(combination) == 0 or sum(combination) % 3:  # not divisible by 3
            continue
        max_combination = sum(x * 10 ** i for i, x in enumerate(sorted(combination)))
        running_max = max(running_max, max_combination)
        running_count += permutation_count(combination)

    return running_count, running_max