Time limit exceeded for Sherlock and Queries Hackerrank challenge 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&lt;stdio.h&gt;

int main()

{

    int n,m,i,j;

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

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

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

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

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

    }

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

        return 0;

}
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 &lt;= m; i++)
    if (b[i] &lt;= n)
        totalProduct[b[i]] = totalProduct[b[i]] * c[i] % MOD
for (divisor = 1; divisor &lt;= n; divisor++)
    // Iterates over all number that are divisible by the divisor
    for (number = divisor; number &lt;= 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.