# Find only two numbers in array that evenly divide each other

Find the only two numbers in an array where one evenly divides the other - that is, where the result of the division operation is a whole number

``````Input Arrays  Output
5 9 2 8       8/2 = 4
9 4 7 3       9/3 = 3
3 8 6 5       6/3 = 2
``````

The brute force approach of having nested loops has time complexity of `O(n^2)`. Is there any better way with less time complexity?

This question is part of advent of code.

• Think of the worst case scenario (no such pair exists). Jan 31, 2018 at 13:37
• What is the upper range for the numbers inside the array? Jan 31, 2018 at 13:48
• The linked question doesn't involve divisors -- it says to subtract the smallest from the largest. Jan 31, 2018 at 15:33
• The the linked question need to be solved, to reveal the divisors part :-). Will post more details here soon. Also there is a garuntee that one pair exists. There is no upper range, so think of max value of an integer.
– mc20
Jan 31, 2018 at 16:30

Given an array of numbers A, you can identify the denominator by multiplying all the numbers together to give E, then testing each ith element by dividing E by Ai2. If this is a whole number, you have found the denominator, as no other factors can be introduced by multiplication.

Once you have the denominator, it's a simple task to do a second, independent loop searching for the paired numerator.

This eliminates the n2 comparisons.

Why does this work? First, we have an n-2 collection of non-divisors: abcde.. To complete the array, we also have numerator x and denominator y.

However, we know that x and only x has a factor of y, so it can be expressed as yz (z being a whole remainder from the division of x by y)

When we multiply out all the numbers, we end up with xyabcde.., but as x = yz, we can also say y2zabcde..

When we loop through dividing by the squared i'th element from the array, for most of the elements we create a fraction, e.g. for a:

y2zabcde.. / a2 = y2zbcde.. / a

However, for y and y only:

y2zabcde.. / y^2 = zabcde..

Why doesn't this work? The same is true of the other numbers. There's no guarantee that a and b can't produce another common factor when multiplied. Take the example of [9, 8, 6, 4], 9 and 8 multiplied equals 72, but as they both include prime factors 2 and 3, 72 has a factor of 6, also in the array. When we multiply it all out to 1728, those combine with the original 6 so that it can divide soundly by 36.

How might this be fixed? More accurately, if y is a factor of x, then y's prime factors will uniquely be a subset of x's prime factors, so maybe things can be refined along those lines. Obtaining a prime factorization should not scale according to the size of the array, but comparing subsets would, so it's not clear to me if this is at all useful.

• Your method might generate false positive denominators, e.g., for [9, 4, 6] it will tell you that 6 is a denominator although it is not. Jan 31, 2018 at 14:02
• You might be correct for /any/ array, but the question specifies there will be one and only one whole division by the numerator/divisor pair. For your array, none exists. Jan 31, 2018 at 15:41
• @Danikov don't get me wrong I like the idea, it's just that you may get false positives. Lest's say we take [9, 4, 6, 2] then you will get 6 and 2 as denominator candidates and have to check for both. There may be scenarios where you will get a lot more ruining you O(n) runtime. Jan 31, 2018 at 16:15
• @Danikov I actually think the idea is valuable. Maybe it is possible to work something out of it or possibly someone is able show that it is still faster than O(n^2). I would leave it. In case it gets negative votes you can get reputation back if you delete it. Jan 31, 2018 at 16:26
• @SaiBot I've realised that [9, 4, 6, 2] is actually invalid as 4/2 and 6/2 means that two pairs divide evenly. Can you think of another counter-example? Feb 1, 2018 at 10:48

I think that `O(n^2)` is the best time complexity you can get without any assumptions on the data.

If you can't tell anything about the numbers, knowing that `x` and `y` do not divide each other tells you nothing about `x` and `z` or `y` and `z` for any `x, y, z`. Therefore, in the worst case you must check all pairs of numbers - equal to `n Choose 2 = n*(n-1)/2 = O(n^2)`.

• Instinctively I think `O(n^2)` is the lower bound too, so +1, but the tricky part is to come up with a more formal proof. Jan 31, 2018 at 15:44

Clearly, we can get `O(n * sqrt(m))`, where `m` is the absolute value range, by listing the pairs of divisors of each element against a hash of unique values in the array. This can be more efficient than `O(n^2)` depending on the input.

``````5 9 2 8

list divisor pairs (at most sqrt m iterations per element m)
5 (1,5)
9 (1,9), (3,3)
2 (1,2)
8 (1,8), (2,4) BINGO!
``````
• what do you mean `by listing the pairs of divisors of each element against a hash of unique values in the array`
– mc20
Jan 31, 2018 at 19:33
• @mc20 I mean checking each pair of divisors to see if one of them is a value in the array. In the example I gave, 2 is a divisor of 8, and since we can test in `O(1)` if 2 exists in the array, we find our solution. Jan 31, 2018 at 19:37
• @SaiBot not sure I understand. Isn't the task to find the only pair in the array where one number is a divisor of the other? All I'm suggesting is to list the divisors and see if one of those divisors is an element in the array. Jan 31, 2018 at 19:54
• Nvm i misunderstood your description. I have to think about it. BTW I did not downvote. Jan 31, 2018 at 20:16
• @גלעדברקן to get `O(1)` , are you suggesting to use a hash set with space compelxity at `O(n)` ?
– mc20
Jan 31, 2018 at 20:16

If you prime factorise all the numbers in the array progressively into a tree, when we discover a completely factored number leaf while factoring another number, we know we've found the divisor.

However, given we don't know which number is the divisor, we do need to test all primes up to divisor's largest factor. The largest factor for any m-digit number is, at most, sqrt(m), while the average number of primes below any m-digit number is m / ln(m). This means we will make at most n (sqrt(m) / ln(sqrt(m)) operations with very basic factorization and no optimization.

To be a little more specific, the algorithm should keep track of four things: a common tree of explored prime factors, the original number from the array, its current partial factorization, and its position in the tree.

For each prime number, we should test all numbers in the array (repeatedly to account for repeated factors). If the number divides evenly, we a) update the partial factorization, b) add/navigate to the corresponding child to the tree, c) if the partial factorization is 1, we have found the last factor and can indicate a leaf by adding the terminating '1' child, and d) if not, we can check for other numbers having left a child '1' to indicate they are completely factored.

When we find a child '1', we can identify the other number by multiplying out the partial factorization (e.g. all the parents up the tree) and exit.

For further optimization, we can cache the factorization (both partial and full) of numbers. We can also stop checking further factors of numbers that have a unique factor, narrowing the field of candidates over time.

• Posted separately as it's significantly different from my other answer. Feb 5, 2018 at 15:45
• Problematic if `m` is large. Also `n (sqrt(m) / ln(sqrt(m))` assumes that you already have a list of primes up to `sqrt(m)`, which (practically) takes an additional `O(sqrt(m) ln ln sqrt(m))`. Depending on the relative size of `n` vs `sqrt(m)` this term may dominate. Dec 2, 2021 at 13:24
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}