Hackerrank Modular Range Queries

Given an array, A=[a0,a1,a2...an], perform queries in the form left
right x y. For each query, print the number of elements satisfying
the following criteria:

• left

• a[i] = y(mod x)

Note: We can write a[i] = y(mod x) as a[i] % x == y in most popular
programming languages.


Input Format


The first line contains two space-separated integers describing the
respective values of (the size of ) and (the number of queries). The
second line has space-separated integers describing the respective
values of . Each of the subsequent lines describes a query in the form
left right x y.


Output Format


For each query, print an integer denoting the number of array elements
satisfying the given criteria on a new line.


Sample Input 0

5 3
250 501 5000 5 4
0 4 5 0
0 4 10 0
0 4 3 2

Sample Output 0

3
2
2

Can this code be optimized in any way?

#include 
#include 
#include 
#include 
#include 
using namespace std;

int main() {
    int n,q;
    cin>>n>>q;
    int A[n];
    for(int i=0;i>A[i];
    while(q--)
        {
       int a,b,x,y,c=0;
        cin>>a>>b>>x>>y;
        for(int i=a;i<=b;i++)
            {
            int t=A[i];
           if(t%x==y)
                c++;
        }
        cout<<c<<endl;
    }
    return 0;
}

Can this code be optimized in any way?

Some of the obvious points:

Remove unnecessary #include statements

Your code doesn't use any stuff from these headers

#include 
#include 
#include 
#include 

So you can remove them.

Don't use using namespace std;

That's generally considered bad practice.

Rather use

using std::cout;
using std::cin;

if you want to avoid typing these out.

Use meaningful variable names

Variable names like

int n,q;
int A[n];

don't tell anything about their semantics.

Standard C++ doesn't support VLA's

Code like

int A[n];

isn't portable. Variable Length Arrays aren't supported by the current c++ standard.

Use

std::vector A(n);

instead to create a dynamically sized array.

Check for successful and valid input

cin>>a>>b>>x>>y;

You never check if the above statement succeeded before proceeding to apply the algorithm.

Better do something like

if(!(cin>>a>>b>>x>>y)) {
    std::cout << "Bad input encountered!" << std::endl;
    return 1;
}

Since

t%x

may segfault when x is zero, you should at east have an assert:

std::assert(x);
if(t%x==y) { // ...
}

Always use braces for scoped blocks

for(int i=0;i>A[i];

should be

for(int i=0;i>A[i];
} // <<<<<<<<

Missing the braces makes that code error prone for changes. It's always better to clarify the scope with conditional or loop statements.

Use prefix incrment (decrement) if you don't need to preserve the previous value

Instead of

for(int i=a;i<=b;i++)
c++;

use

for(int i=a;i<=b;++i)
++c;

You obviously don't need the old value preserved by the postfix increment operations.

Performance of formatted text extraction


The values of of n,q,a,x,y,b are ranging from 1 to 40000. so it gets the timeout therefore it needs to further optimised

As for your performance concerns:

Formatted text extraction in c++ is costly. You may get a performance improvement just using scanf() in this case.

While

cin>>a>>b>>x>>y;

applies four function calls

scanf("%d %d %d %d",a,b,x,y);

would be only one call. Also the internal implementation of the formatted text extraction syntax boils down to some scanf() like functions for most of the c++ compilers anyways.

StackExchange Code Review Q#158071, answer score: 7