CODEWITHSUNDEEP
algorithmdata-structures
Sunny
Sunny

Reputation: 381

Finding the Closest Divisable in an Array

I am having an Array of N integer where N<= 10^6 for every index i i have to find the closest left neighbor of 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 i.e 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 probably O(nlogn)

Upvotes: 4

Views: 192

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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

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 may find it faster to do some precomputing of factorizations.

The algorithm works by using D[x] to store the position j of the most recent number A[j] that is a multiple of x.

Upvotes: 3

Related Questions