Find smallest integer in array which is a divisor of all previous integers

Question

I've been solving previous years' exam questions for practice and I came across one problem that I /suspect/ I can't solve without a number theory relation that I am not aware of.

The problem is:

Given an array of N integers, find the smallest integer which is a divisor of all the previous integers.

Now the problem is that if I can't cache any results from the modulo operations, then the complexity becomes O(n^2) which doesn't run fast enough to pass the problem's automatic test since there is a time limit and a potential size of 3 million elements.

Are there any f and g for which f(d, g[a1, a2, a3, a4, ..., an])) is true if and only if d | a1, d | a2, d | a3, ..., d | an ? If not, do you guys have any other suggestions on approaches to the problem?

Any help is appreciated!

Answer 1

an divides all previous elements if and only if it divides the greatest common divisor of those elements.

So you need to keep track of gcd(a1, a2, ..., an) and the minimum an for which an | gcd(...).

Answer 2

Just leaving this here:

I solved the problem by noting that if we start from the ith element and check continuously the previous elements until the jth, then all the elements between are multiples of the ith element. If the condition doesn't hold for all the previous elements then it also won't hold if we start from the elements i-1 to j. We can start again from the jth element and repeat the process. Therefore starting from the last element we are guaranteed to find a solution. This also takes care of finding the minimum of the solutions since all the other solutions must lay in the previous elements and they have to be multiples of the first solution.