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.

0 1 2 3 4 5 6
0 1 0 0 0 1 1 0
1 0 0 0 0 0 0 0
2 0 0 1 0 0 0 1
3 0 1 0 1 0 0 0
4 0 0 0 0 0 0 0

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

0 1 2 3 4 5 6
0 1 1 1 1 2 3 3
1 0 0 0 0 0 0 0
2 0 0 1 1 1 1 2
3 0 1 1 2 2 2 2
4 0 0 0 0 0 0 0

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 <bits/stdc++.h>

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<vector<int> >& 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<vector<int> > 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)

Leave a Comment