Find only two numbers in array that evenly divide each other

Question

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.

Answer 1

Given an array of numbers A, you can identify the denominator by multiplying all the numbers together to give E, then testing each i^th element by dividing E by A_i². 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 n² 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 y²zabcde..

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:

y²zabcde.. / a² = y²zbcde.. / a

However, for y and y only:

y²zabcde.. / 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.