Queries to Count Array Elements Greater Than or Equal to a given Number with Updates

Approach

A simple approach to solve this is to simply iterate over the array for each query and count the number of elements greater than or equal to the query[i] and then subtract M from each of them.

Algorithm

1. Declare an array ans[] for storing final answers.

2. Iterate over the query[] array and do the following for each query[i]:

a). Traverse over the array A[]. Check if the current element is greater than or equal to the query[i]. If yes, then increment the count and subtract M from the current element of A[]

3. Print the final answers.

Program

#include <bits/stdc++.h>
using namespace std;
 
void solve(vector<int>& a, vector<int>& query, int M){
    int N = a.size(), Q = query.size();
 
    vector<int>ans(Q, 0);
 
    for(int q=0; q<Q; q++){
        int count = 0;
        for(int i=0; i<N; i++){
            if(a[i] >= query[q]){
                count++;
                a[i] -= M;
            }
        }
 
        ans[q] = count;
    }
 
    for(int i=0; i<Q; i++) cout << ans[i] << " ";
    cout << endl;
}
 
int main(){
    int tt; cin >> tt;
    while(tt--){
        int N, Q, M; cin >> N >> Q >> M;
 
        vector<int>a(N);
        for(int i=0; i<N; i++) cin >> a[i];
 
        vector<int>query(Q);
        for(int i=0; i<Q; i++) cin >> query[i];
 
        solve(a, query, M);
    }
    return 0;
}

INPUT

2
 
4 3 1
1 2 3 4
4 3 1
 
3 2 2
1 2 3
3 3

OUTPUT

1 2 4
1 0

Time Complexity

The time complexity of the above approach is O( Q * N ). 

Space Complexity

The auxiliary space complexity of the program is O( N  ). 

FAQs

1. What is a Segment Tree?
   A Segment tree is a data structure that stores information about array segments and allows efficient processing of range queries along with updates.
    
2. What is the time complexity of insertion and query in a Segment Tree?
   The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
    
3. What is the advantage of Fenwick tree over Segment tree?
   The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
    
4. What is the disadvantage of the Fenwick tree over the Segment tree?
   We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

Key Takeaways

Cheers if you reached here!! 

This article discussed an intriguing problem using the arrays. Array-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Check out this problem - Longest Subarray With Sum K 

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!