Finding the closest dividend in an array

Question

I have an array from N integer, where N<= 10^6 for every index i I need to find the nearest left neighbor i, such that A[j]%A[i]==0 0<j<i

Example

 3 4 2 6 7 3 Nearest Neighbor array -1 -1 1 -1 -1 3 As for last element ie 3 6%3==0 and index of 6 is 3 so ans is 3 similar for 2 nearest neighbor is 4 

Brute force approach

 int[] Neg = new int[n]; Arrays.fill(Neg,-1); for(int i=1;i<n;i++) for(int j=i-1;j>=0;j--) if(A[j]%A[i]==0){ Neg[i]=j; break; } 

This O(n^2) approach and will fail how can I come up with a better approach, possibly O (nlogn)

Answer 1

There is a simple O (n.sqrt (n)) algorithm:

 Initialize an array D to all -1. For i = 1,2,...,n Let a = A[i] Output D[a] For each divisor d of A[i]: set D[d] = i 

You can find all the divisors of a number in O (sqrt (n)) with a simple loop, or you can quickly find some preliminary factorization calculation.

The algorithm works with D [x] to save the position j of the last number A [j], a multiple of x.