2
\$\begingroup\$

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

Example:

6
2 3 5 7 4 9
2
4 5
3 7

Output:

2
3

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.

\$\endgroup\$
  • 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 '16 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.