# How to Optimise the following algorithm? maximum good value of an element in an array

I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an array element $$A_i$$ is defined as the total no. of Valid indices $$𝑗<𝑖$$ such that $$𝐴_𝑗$$ is divisible by $$𝐴_𝑖$$. My approach is as follows,

    int maximum=-1;
for(int i=n-1;i>=0;i--){
int count=0;
for(int j=0;j<i;j++){
if(arr[j]%arr[i]==0)
count++;
}
maximum=max(count,maximum);
}
print(maximum);

• @Juho I want to Optimise my algorithm such that I can solve it in less than a 1 sec for the constraints, $$1≤T≤10$$ $$1≤arraysize≤10^5$$ $$1≤A_i≤10^6$$ – Akash Tadwai Oct 6 at 18:01

Depending on the input values the following strategy might work: keep an array $$C$$ of $$10^6$$ elements where $$C[i]$$ will store the number of times number $$i$$ appears in the elements of the input array that have already been processed.

Initially $$C$$ is identically 0, then you consider the elements $$A_i$$ one at a time. When you are processing the $$A_i$$ you can compute the "good value" by taking the sum of all $$C[k A_i]$$ for $$k=1,\dots,\lfloor 10^6 / A_i \rfloor$$. Then, increment $$C[A_i]$$.

At the end of the process return the maximum sum.

A more refined strategy is that of handling separately small and large values of $$A_i$$. If $$A_i \ge 1000$$ then the above algorithm check at most $$10^3$$ entries in $$C$$. If $$A_i < 1000$$ then you can find the number of its multiples by checking and keeping track of how many of the input elements seen so far are divisible by the numbers between $$1$$ and $$1000$$. This also requires $$\approx 1000$$ operations. So you'll be performing $$\approx 2 \cdot 10^5 \cdot 10^3$$ operations as opposed to $$10^{10}$$ of your algorithm.

An even better strategy is to keep an array $$D$$ where $$D[n]=j$$ means that $$j$$ of the numbers seen so far have $$n$$ a divisor. Since the number of divisors grows slowly (as $$O(\log n / \log \log n)$$, and it is always at most $$240$$ for your values) this strategy will only increment a few values per input number (less than 14 on average, assuming an uniform input distribution. See here for a plot of the number of divisors of the first $$10^5$$ integers). The leaves you with a number of operations of the order of $$10^6$$ to $$10^7$$.

The problem is now that of enumerating, for each number $$n$$, its divisors efficiently. But you can just do this as a preprocessing step by multiplying each $$i=1,\dots,10^6$$ by consecutive integers $$k$$ until it exceeds $$10^6$$. For each such $$k$$ add $$i$$ to the list of divisors of $$k \cdot i$$. This could even be done once-for-all and hardcoded in your algorithm.

• The method is somewhat difficult to understand, can you post a pseudo code or code for this so that I can understand it easily? – Akash Tadwai Oct 7 at 5:22
• Something along these lines. In the code divisors is an array containing all the divisors of $1$, followed by all the divisors (in increasing onder) of $2$, ..., up to all the divisors of $10^6$, and $ndiv[i] = \sum_{j=1}^{i-1} d(j)$, where $d(j)$ is the number of divisors of $j$. – Steven Oct 7 at 10:14