Time limit exceeded for Sherlock and Queries Hackerrank challenge

Question

Here is my C solution for Sherlock and Queries @ Hackerrank.

Watson gives to Sherlock an array: \$A_1, A_2, ..., A_N\$. He also gives to Sherlock two other arrays: \$B_1, B_2, ..., B_M\$ and \$C_1, C_2, ..., C_M\$.

Then Watson asks Sherlock to perform the following program:

for i = 1 to M do
    for j = 1 to N do
        if j % B[i] == 0 then
            A[j] = A[j] * C[i]
        endif
    end do
end do

Can you help Sherlock and tell him the resulting array A? You should print all the array elements modulo \$(10^9 + 7)\$.

Input Format

The first line contains two integer numbers \$N\$ and \$M\$. The next line contains \$N\$ integers, the elements of array A. The next two lines contains \$M\$ integers each, the elements of array B and C.

Output Format

Print \$N\$ integers, the elements of array A after performing the program modulo \$(10^9 + 7)\$.

Constraints

\$1 ≤ N, M ≤ 10^5\$
\$1 ≤ B[i] ≤ N\$
\$1 ≤ A[i], C[i] ≤ 10^5\$

Sample Input

4 3
1 2 3 4
1 2 3
13 29 71

Sample Output

13 754 2769 1508

How should I optimize it as it is showing teminated due to time out?

#include<stdio.h>

int main()

{

    int n,m,i,j;

    scanf("%d %d ",&n,&m);

    long int a[n+1],b[m+1],c[m+1];
    for(i=1;i<=n;i++)
        scanf("%ld",&a[i]);

    for(i=1;i<=m;i++)
        scanf("%ld",&b[i]);

    for(i=1;i<=m;i++)
        scanf("%ld",&c[i]);

    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(j%b[i]==0)
            {
                a[j]=(a[j]*c[i])%1000000007;
            }
        }

    }

    for(i=1;i<=n;i++)
        printf("%ld ",a[i]%1000000007);

        return 0;

}

Answer 1

The time complexity of your solution is \$ O(NM) \$. It is too slow. You need a more efficient algorithm. Here is a pseudo code of a better one:

// Reads the input.
n = read_input()
m = read_input()
a = read_input()
b = read_input()
c = read_input()
// Creates an auxilary array to remove duplicates from b 
totalProduct = an array of n + 1 elements filled with 1
for (i = 1; i <= m; i++)
    if (b[i] <= n)
        totalProduct[b[i]] = totalProduct[b[i]] * c[i] % MOD
for (divisor = 1; divisor <= n; divisor++)
    // Iterates over all number that are divisible by the divisor
    for (number = divisor; number <= n; number += divisor)
        a[number] = a[number] * totalProduct[divisor] % MOD
print(a)

The correctness of this algorithm is obvious (it simply does what is written in the problem statement). So why is it efficient? It is fast because its time complexity is $$ O\big(M + { N \over 1 } + { N \over 2 } + { N \over 3 } + \dotsb + { N \over N }\big) = O(M + N \log N). $$ Why do we need to remove duplicates from b? If we don't do it, the time complexity will be \$ O(M + N^2) \$ if all elements of b are equal to 1.

Answer 2

This particular piece of code has a rather obvious source of inefficiency: the inner loop does nothing most of the time. A quick way to get a big improvement in the runtime is to change the inner loop so that it doesn't iterate over all possible values of j, but only those values where the loop will do something.

In more general problems this can be more complicated and might require some precomputation, but here it's easy:

int step = B[i];
for (int j = step; j <= M; j += step) {
    // do stuff
}

There are other, more complicated optimizations you could look into, but this one will get a big improvement for little work, especially if the B array contains large numbers.

(P.S. the loop above will have undefined behavior if B[i] is greater than half of INT_MAX and is no greater than M. If you care about being correct in this special case, you'll have to go through some extra effort to pay attention to it)

(P.P.S. the loop above does the wrong thing of B[i] is negative. If you care about being correct in this special case, you'll have to go through some extra effort to pay attention to it)

---

Aside: the point of the variable step, is to guard against the possibility that the optimizer fails to figure out that the value of B[i] does not change during the inner loop. If the optimizer fails to realize this and you use B[i] directly in the for loop, your loop will run really slowly.

Why, you ask, could anyone ever get the idea that B[i] might change? It's because A and B could potentially point to overlapping arrays, and thus A[j] and B[i] might actually refer to the same value, and so changing the former will change the latter.

With your code, exactly as it is written, a decent optimizer should figure out that A and B don't overlap, but it doesn't really hurt to make a habit of taking this extra precaution, and there are a number of ways it can save you.