While solving one question I got stuck with a time limit error. The main objective in question is to count numbers in an array \$A\$ that are either divisible by \$P\$, \$Q\$ or both.
The first line contains a single integer \$N\$ denoting the size of array \$A\$. The next line contains \$N\$ space separated integers, where the \$i\$th integer denotes \$A[i]\$.
The next line contains a single integer \$T\$ denoting the number of queries Monk poses to you. Each of the next \$T\$ lines contains 2 space-separated integers \$P\$ and \$Q\$.
6 2 3 5 7 4 9 2 4 5 3 7
The naive approach from my side is this:
a = int(raw_input()) # Length of an array b = map(int,raw_input().split()) # Array of size a c = int(raw_input()) # Number of query for _ in xrange(c): d,e = map(int,raw_input().split()) # 2 numbers count = 0 for i in b: if i%d==0: count+=1 elif i%e==0: count+=1 print count
I guess it is taking linear time \$O(n) + c\$ which can be improved to \$O(log(n))\$ but I am not sure what's the best way to do it or how to implement it.