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.

Input format:

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\$.


2 3 5 7 4 9
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:
        elif i%e==0:
    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.

  • 4
    \$\begingroup\$ Not giving the link to the problem statement at hackerearth deprives readers of a piece of information that might be a giveaway: the category is Integer Factorization & Math Practice Problems. In performance analysis, in may prove necessary to distinguish preparation and queries. \$\endgroup\$
    – greybeard
    Dec 6, 2016 at 19:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.