Return to Question

While solving one Hackerearth 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.

While solving one Hackerearth 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.

While solving one Hackerearth 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.

While solving one Hackerearth 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.

While solving one Hackerearth 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.

While solving one Hackerearth 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.