# Count of Array elements in given range with remainder X when divided by K for Q queries

Given an array arr[] of size Nan integer K and Q queries, each of form {x, l, r}. For each query, the task is to find the count of all elements in index range [l, r] which have remainder x when divided by K.

Examples:

Input: arr[] = {15, 28, 72, 43, 20, 0, 97}, K = 5, queries[] = {{3, 0, 3}, {0, 0, 6}, {6, 2, 4}}
Output: 2, 3, 0
Explanation: For the first query, there are 2 elements in the range [0, 3] whose remainder is 3 (28, 43).
Similar 3 elements in range [0, 6] whose remainder is 0 (15, 20, 0).
In the third query, elements whose remainder are 6 should be found.
But for the given K = 5 possible remainders are only [0, 4]. So for any x >= K, answer will be 0.

Input: arr[] = {2, 4, 6, 7, 5}, K = 3, queries[] = {{2, 1, 4}}
Output: 1

Method 1: A simple approach is, for each query, iterate through l to r and count all elements whose remainder is x.

Time Complexity: O(N * Q)
Auxiliary Space: O(1)

Method 2: This problem can also be solved with help of precalculation based on the following idea:

Precalculate what will be the remainder, when arr[i] is divided by K and store them in a matrix (say mat[]) where mat[i][j] represents the remainder of arr[j] is i when divided by K.
Now prefix sum of ith row of the matrix gives the count of elements which will have remainder i when divided by K. Therefore, after prefix sum mat[i][j] will represent total count of elements till jth index having remainder i when divided by K.
So for a query {x, l, r} the answer will be (mat[x][r] – mat[x][l] [+1 if arr[l]%K is x])

Follow the illustration below for a better understanding of the construction of the matrix.

Illustration:

Consider arr[] = {15, 28, 72, 43, 20, 0, 97}, K = 5

Make a 2D matrix named precomputeof size (K*N)and initialize it with 0.
For the ith element mark precompute[arr[i]%K][i] = 1do this for all i which states that the ith element has remainder arr[i]%K.

For the given example our precompute matrix will look like the following where row: remainder, column: index num.

Then for each calculate row prefix sum. Now matrix will look like this:

Here precompute[0][6] denotes that till 6th index there are a total of 3 elements which will have reaminder 3 when divided by 5.

Follow the steps mentioned below to implement the idea:

• Create the 2D array (say precompute).
• Construct the array as mentioned above.
• Traverse the queries:
• For each query calculate the number of elements as per the formula shown above and store that in the answer array.
• Return the array having the answers.

Note: This method is more efficient only when the number of queries is greater than K.

Below is the implementation of the above approach:

## C++

 ` ` `#include ` `using` `namespace` `std;` `const` `int` `MXN = 2e5;` `int` `precompute[100][MXN];` ` ` `void` `precomputation(``int` `arr[], ``int` `n, ``int` `k)` `{` `    ` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``precompute[arr[i] % k][i] = 1;` ` ` `    ` `    ``for` `(``int` `i = 0; i < k; i++) {` `        ``for` `(``int` `j = 1; j < n; j++) {` `            ``precompute[i][j]` `                ``+= precompute[i][j - 1];` `        ``}` `    ``}` `}` ` ` `vector<``int``> findCount(``int` `arr[], ``int` `K, ``int` `N,` `                      ``vector >& queries)` `{` `    ``vector<``int``> res;` ` ` `    ` `    ``memset``(precompute, 0, ``sizeof` `precompute);` ` ` `    ` `    ``precomputation(arr, N, K);` `    ``for` `(``int` `i = 0; i < queries.size(); i++) {` `        ``int` `x = queries[i][0];` `        ``int` `l = queries[i][1];` `        ``int` `r = queries[i][2];` `        ``if` `(x >= K) {` `            ``res.push_back(0);` `            ``continue``;` `        ``}` `        ``int` `count = precompute[x][r]` `                    ``- precompute[x][l]` `                    ``+ (arr[l] % K == x);` `        ``res.push_back(count);` `    ``}` `    ``return` `res;` `}` ` ` `int` `main()` `{` `    ``int` `arr[] = { 15, 28, 72, 43, 20, 0, 97 };` ` ` `    ``int` `K = 5;` `    ``int` `N = ``sizeof``(arr) / ``sizeof``(arr[0]);` `    ``vector > queries{ { 3, 0, 3 },` `                                  ``{ 0, 0, 6 },` `                                  ``{ 6, 2, 4 } };` ` ` `    ``vector<``int``> ans` `        ``= findCount(arr, K, N, queries);` `    ``for` `(``int` `x : ans)` `        ``cout << x << ``" "``;` `    ``return` `0;` `}`

Time Complexity: O(Q + K*N)
Auxiliary Space: O(K*N)