Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$.

For example, given the array

36 40 16 24 27 12 9 4

we see that element 4 has the highest number of multiples (5) as per the given conditions, so the answer is 5.

My approach: I used brute force to solve this. I used nested loops to solve this. The first loop from the last element and the second loop from the first element to the second to last element.

Can you help me improve the running time?

  • $\begingroup$ How large can your integers be? $\endgroup$ – md5 Oct 6 '19 at 20:53
  • $\begingroup$ integers can range from 1 to 10^6 and size of array can range from 1 to 10^5 $\endgroup$ – ANKIT SINGHA Oct 7 '19 at 4:15

Hint: note that if there are duplicates, we are basically only interested in the last occurrence of each value. Now if you maintain an array $C$ of size $\max_i A[i]$ such that at the $i$-th iteration of your algorithm $C_k=|\{j\le i, A_j=k\}|$, how can you compute the number of multiples of $A[i]$ to the left of $i$ so that the overall complexity is not too high?


Maintain an array Composite_in_Array[n] and Multiples[n] initialize with zero.

for i=n-1 to i>=0
  if( Composite_in_Array[i] !=0 )
    for j=i-1 to j>=0
       if( A[j] % A[j] == 0 )

Find the index with largest value in Multiples[]. Corresponding value in A[] will be your answer.

This approach eliminates the cost of finding multiples of numbers which are already divisible by a number on their right.

After the first few iterations, the arrays would look like this. So on the next iteration

A                    36 40 16 24 27 12 9 4
Multiples            0   0  0  0  0  0 0 5
Composite_in_Array   1   1  1  1  0  1 0 0

A                    36 40 16 24 27 12 9 4
Multiples            0   0  0  0  0  0 3 5
Composite_in_Array   1   1  1  1  1  1 0 0

The loop will not look for any more divisors since they can't be a candidate for having highest multiple counts as all their multiples are also divisible by their divisor.


what is the constraint size ? depending on the size you can select which algorithm to use O(n^2) is not preferable .O(n^2) refers to using nested for loops

  • 1
    $\begingroup$ i did using nested for loops but it's exceeding the time limit s the input size is n=10^5...so u have to think about some optimization $\endgroup$ – ANKIT SINGHA Oct 5 '19 at 13:59
  • $\begingroup$ thats what i am saying you need to use algorithm of O(nlogn) complexity example of O(nlogn) complexity is merge sort $\endgroup$ – pkchamp gaming Oct 5 '19 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.