Find all numbers that are factors of one array and factor into the second array, then print their count

Question

I'm working on a solution to the Following problem on Hackerrank, and I seem to have found a function that works for the purpose. However, I feel as though this is a very overdesigned solution to a problem that appears, at first glance, to be simple. This is what I've come up with so far:

This code takes in two arrays, finds every pair of numbers from 1 to 100, multiplies them together, and tests if the product is a factor of all elements in the first array. If so, it appends the product to the fact array. Then, it tests every element in the fact array and checks if the element evenly divides every element in the second array. If so, it loads that element into a new list. Finally, it returns the length of the new list

I've run the code through a few static analyzers but they became unhelpful after a point. I'm looking for ways to cut this code down and reduce its complexity and depth. Any comments or criticisms are welcome!

Apologies if I've made any mistakes in my question-asking etiquette here, feel free to let me know if this needs more context and thanks in advance!

def get_total_x(input_factors: int, test_numbers: int) -> int:
    fact = list()
    output = list()
    for mult1 in range(100):
        for mult2 in range(100):
            # find all multiples of mult1 and mult2 that can be factored
            # into all numbers in a, while ignoring zero.
            if all(v == 0 for v in [(mult1 * mult2) % factor for factor in input_factors]) and (mult1 * mult2 != 0):
                fact.append(mult1 * mult2)
    seen = set()
    seen_add = seen.add
    # remove duplicates, may be able to cut out?
    fact = [x for x in fact if not (x in seen or seen_add(x))]
    for test in fact:
        # check for all numbers from the previous loop that divide b cleanly.
        if all(w == 0 for w in [factor2 % test for factor2 in test_numbers]):
            output.append(test)

    return len(output)


if __name__ == '__main__':

    arr = (2, 4)

    brr = (16, 32, 96)

    total = get_total_x(arr, brr)

    print(total)

Answer 1

Redundant calculations

You calculate mult1 * mult2 three times. Instead, do this once, assign it to a variable, and use that.

---

Since you want to never want to calculate when a value is 0, you can set the start of range to 1.

range(1, 101) # 1 -> 100, since (inclusive, exclusive)

Now you can remove that (product != 0) check.

Type hints

At first, it looks like the function accepts two integers. In reality, it accepts two tuples of integers. Consider doing the following:

from typing import Tuple

def get_total_x(input_factors: Tuple[int], test_numbers: Tuple[int]) -> int:

This makes it clear that you want tuples of integers as parameters, instead of a single integer.

Using sets

You use a set, but you don't actually use the set. You're trying to add values to the set that aren't already there, or that you can add to the set. Instead of having that list comprehension, simply cast fact into a set. Does the exact same thing.

fact = set(fact)

Magic numbers

What is the significance of 100? I see in your question you explain, but not in the code. I would assign this to a variable to make it more clear.

Answer 2

Algorithm

You do a nested loop which is completely without reason

for mult1 in range(100):
    for mult2 in range(100):
        # find all multiples of mult1 and mult2 that can be factored
        # into all numbers in a, while ignoring zero.
        if all(v == 0 for v in [(mult1 * mult2) % factor for factor in input_factors]) and (mult1 * mult2 != 0):
            fact.append(mult1 * mult2)

In the loop you use the counters only in a way mult1 * mult2. This results in

• 199 element of the value 0 which you remove in a special clause
• the biggest value being tested to be 99*99 which is 9801 which is far bigger than the maximum number to factor
• typical realistic numbers being duplicated (e. g. 16 is generated 5 times)
• 10000 tests for less than 100 realistic candidates

For the zeros you have a special clause and a comment for clarification. You should not generate the zeros beforehand, loop over range(1, ...)

If wee look at the problem we see that a and b are in range(1, 101). Any solution must be greater or equal to max(a). It also must be less or equal to min(b). So it is completely sufficient to search range(max(a), min(b)+1). We can improve the efficiency even a little more and step by max(a).

Removing duplicates

If the looping is done right we do not need to remove duplicates any more. However, if you have to do de-duplication decide whether you need to preserve the order. In your code you do de-duplication while maintaining order. As maintaining order is not needed in this problem, you can simply create a set from the list. Depending on the application you may want to create a list from the set again.

fact = set(fact)

Names

It is helpful to stick to the names given in the problem. That maintains readability.

We end up in a function like

def get_total_x(a: Tuple[int], b: Tuple[int]) -> int:
    numbers = []
    for i in range(max(a), min(b) + 1, max(a)):
        if all(i % a_i == 0 for a_i in a) and all(b_i % i == 0 for b_i in b):
            numbers.append(i)
    return len(numbers)

The function still misses documentation (and a better name). Type hints see @Linnys answer.

Answer 3

Instead of writing a nested for loop, directly write it as a list comprehension. In addition, you can start the second loop at the value of the outer variable in order to remove some double counting. This reduces the numbers to iterate over from 9801 to 4950, by a factor two, since you don't have both e.g. 2 * 6 and 6 * 2. However, some values still appear more than once (since e.g. 12 is 2 * 6, but also 3 * 4 and 1 * 12), so you still need a set comprehension:

limit = 100
fact = {a * b for a in range(1, limit) for b in range(a, limit)
        if all(i % factor == 0 for factor in input_factors)}

Note that I directly used i % factor in the loop in all. No need to involve an addition list comprehension to iterate over.

You should also just count the results, don't append them to a list if you only care about its length:

return sum(1 for f in fact if all(test % f == 0 for test in test_numbers))