Maximum number of multiples of an array element preceding it

Question

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?

• md5: How large can your integers be?
• ANKIT SINGHA: integers can range from 1 to 10^6 and size of array can range from 1 to 10^5

Answer 1

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?

Answer 2

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 )
 Composite_in_Array[j]=1;
 Multiples[i]++;
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.

• gnasher729: 2nd line: If composite[i] equals 0 instead of "not equals".

Answer 3

Take roughly Devesh's answer with one addition:

For each integer from Array[0] to Array[N-1], we find the prime factors, and for each prime factor we create a linked list of all numbers with that prime factor, and the count of items in the list. (I'm assuming that N is so large that it can be done in O (N^2)).

Then run Devesh's algorithm. To speed up, we look at the prime factors of A[i], remove A[i] from all the lists of numbers with prime factors, then pick the list with the fewest elements, and examine those numbers only. For example, if A[i] = 2 * 3^2 * 113, then quite likely there are only few numbers with a prime factor 113, so we can check them quickly.

If the numbers are large so that factoring them completely is slow compared to N, then we don't need to do a complete factoring. For example, if we count numbers with one of the smallest 64 primes as a factor, and then count numbers having a larger factor, the algorithm still works. The factoring is more efficient although the counting is less efficient.

Answer 4

O(nlogn) approach

• First maintain a count array cnt[] such that cnt[i] stores frequency of i in your array, as well as a set to keep distinct numbers of your array
• Then go through each number in the set, go through its multiples and add up the cnt[]

Code (Python)

array = [36, 40, 16, 24, 27, 12, 9, 4]
frequency = [0] * 1000001
distinct = set()
for element in array:
 frequency[element] += 1
 distinct.add(element)
ans = 0
for element in distinct:
 current = 0
 for multiple in range(element, 1000001, element):
 # equivalent to
 # for (int multiple = element; multiple <= 1000000; multiple += element)
 current += frequency[multiple]
 ans = max(ans, current)
print (ans)

Complexity is O(MAXN*logn) worse case because the elements are distinct and the complexity is O(1000000/1+1000000/2+...+1000000/m) and m can be n so O(MAXN*logn)=O(1e6*20) by harmonic series

Note: If you don't want to use a set, maintain another seen array as well as a distinct array. Then before you insert simply check if seen[element] is true.

EDIT: OOPS I MISREAD THE PROBLEM I AM SORRY

Since you only want to count multiples preceding it, you can modify the code such that you store the position of the occurrences, not just the frequency. (i.e. frequency[i] stores [position where i occurred]). You would also need to store the latest position a number appears in the distinct set, not just te number itself.

Then instead of current += frequency[multiple], you should first binary search for the largest index that's <= multiple, then add the number of terms.

The complexity analysis will be left as an exercise :)