Hackerrank Modular Range Queries

Question

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 < i < right
• 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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
 int n,q;
 cin>>n>>q;
 int A[n];
 for(int i=0;i<n;i++)
 cin>>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;
}

• πάντα ῥεῖ: What are your performance concerns actually? Could you elaborate about these?
• asphalt: 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
• asphalt: @Peilonrayz can this code be further optimized.

Answer 1

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 <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

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<n;i++)
 cin>>A[i];

should be

for(int i=0;i<n;i++) { // <<<<<<<
 cin>>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.

• Maikel: The performance section of your review is really weak. This is a question about asymptotic behaviour and not something about scanf vs cin. The rest of the review has is pretty valid tho.

Answer 2

You are using brute force approach to solve the problem, but with given input constraints, your solution is more likely to time out during system test. This can be solved by segment trees or binary indexed trees which can answer queries in \$O(logn)\$ time, and for q queries, complete time complexity would be \$O(q*logn)\$. This will easily pass the final system test.

Basic operations supported by segment tree are:

1. updating single element
2. updating range of elements
3. querying information about range of elements.

Reference : http://letuskode.blogspot.in/2013/01/segtrees.html