Calculate element which is most divisible by all elements in the same array (better than O(n^2))

Question

I have done this example in O(n^2). Given a array, I do the following:

max_key = 0
for k in set(keys):
    count = 0
    for divisor in keys:
        if key < divisor: break
        if key% divisor == 0: count += 1
    if count > max_key: max_key = count
print(max_key)

An example of this would be:

keys = [2,4,8,2]

Then the element most divisible by all elements in the keys is 8 because there are 4 elements (2,2,4,8) that can divide 8.

Can anyone suggest an approach better than O(n^2) ?

Answer 1

I think you could change one of the n into a factor that is pseudo-polynomial by inserting the numbers into a dict (amortized, expected).

keys = [2,4,8,2]

# https://stackoverflow.com/a/280156/2472827
# max key, O(keys)
max_key = max(keys)

# https://stackoverflow.com/a/6582852/2472827
# occurrence counter, O(keys)
count = dict()
for k in keys:
    count[k] = count.get(k, 0) + 1

# https://stackoverflow.com/a/18634675/2472827
# transform into an answer counter, O(keys)
answer = dict.fromkeys(keys, 0)

# https://stackoverflow.com/a/1602964/2472827
# fill the answer, O(keys * max_key/min_key)
for a in answer:
    max_factor = int(max_key / a)
    for factor in range(1, max_factor + 1):
        number = a * factor
        if number in answer:
            answer[number] += count[a]

# O(keys)
a = max(answer, key = answer.get)
print answer[a], "/", len(keys), "list items dividing", a

I think it works in O(n * max_n/min_n) (expected.) In this case, it is pretty good, but if you have a high dynamic range of values, it's easy to make it go slow.

Answer 2

keys = [2,4,5,8,2]

We can try something like memoization (from dynamic programming) to speed up while not doing any repeated calculations.

First, let's keep a hashmap, which stores all the divisors for a number in that array.

num_divisor = {} # hashmap

We keep another hashmap to store if a value is present in the array or not (count of that number).

cnt_num = {2: 2, 4: 1, 5: 1, 8: 1}

Now, we run prime sieve up to max(keys) to find the smallest prime factor for each number up to max(keys).

Now, we traverse the array while factoring out each number (factoring is only O(logn) given we know the smallest prime factor of each number now),

pseudo-code

for a in keys:
  temp_a = a # copy
  while temp_a != 1:
    prime_factor = smallest_prime_factor[temp_a]
    temp_a = temp_a / prime_factor
    if solution for new temp_a is already known in num_divisor just update it from there (no recalculation)
    else:
      if new temp_a is in keys, we increment the solution in num_divisor by 1 and continue 

overall complexity: max(keys) * log(max(keys)) [for seive] + n * log(max(keys))

This should work well if the keys are uniformly distributed. For cases like,

keys = [2, 4, 1001210], it will do lots of unnecessary computation, so in those cases, it is better to avoid the sieve and instead compute the prime factors directly or in extreme cases, the pairwise divisor calculation should outperform.

Answer 3

You could potentially improve your code by:

• Account for duplicates by putting keys in a counting map first (e.g. so you don't have to parse the '2' twice in your example). This helps if there's a lot of repetition.
• If the square root of the value being checked is smaller than the number of keys, check up to the square root of the value being checked (together with the value being checked divided by its divisors). This helps if there are lots of numbers having square roots that are smaller than the total number of elements.

E.g. If we're checking 30 and the list is big, we only need to check: 1 up to 5 to see if they divide 30 and their counts, as well as 30 divided by any of its divisors in this range (30/1=30, 30/2=15, 30/3=10, 30/5=6) and their counts.

E.g. if we're checking 10^100+17, and there are 10 items total, just check each of them in turn.

Neither of these affect worst case analysis since an adversary could choose inputs where they're useless. They may help in the problems you need to solve depending on your inputs, and may help more broadly if you have some guarantees on the inputs.

Answer 4

Let's think about this a different way: instead of an array of numbers, consider a directed acyclic graph where each number becomes a vertex in the graph, and there is an edge from u → v if and only if u divides v. The problem is now to find a vertex with the greatest in-degree.

Note that we can't actually count the in-degree of a vertex directly in less than Θ(n) time, so the naive solution is to count the in-degree of every vertex in Θ(n²) time. To do better than Θ(n²), we need to take advantage of the fact that if there are edges u → v → w then there is also an edge u → w; we get knowledge of three edges for the price of two divisibility tests. If there are edges u → v → w → x then three divisibility tests can buy us knowledge of six edges in the graph, and so on.

However, crucially, we only get "free" information about edges if the numbers we test are divisible by each other. If we do a divisibility test and the result is negative, we get no "free" information about other possible edges. So in the worst case, there is only one edge in the graph (i.e. all the numbers in the array are not multiples of each other, except for one pair). For an algorithm to output the correct result, it must find the single number in the array which has a divisor in the array, but each divisibility test which doesn't find this pair gives no "free" information. So in the worst case, we would indeed have to test every pair to find the correct answer. This proves that a worst-case time complexity of Θ(n²) is the best you can do in the general* case.

^{*In case the array elements are bounded, then a pseudopolynomial algorithm could plausibly do better.}