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++){
| cite | improve this question | | | | |
  • $\begingroup$ @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$$ $\endgroup$ – Akash Tadwai Oct 6 '19 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.

| cite | improve this answer | | | | |
  • $\begingroup$ The method is somewhat difficult to understand, can you post a pseudo code or code for this so that I can understand it easily? $\endgroup$ – Akash Tadwai Oct 7 '19 at 5:22
  • $\begingroup$ 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$. $\endgroup$ – Steven Oct 7 '19 at 10:14

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.