1.
Introduction
2.
Problem Statement
2.1.
INPUT
2.2.
OUTPUT
2.3.
Explanation
2.4.
INPUT
2.5.
OUTPUT
2.6.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
INPUT
3.4.
OUTPUT
3.5.
Time Complexity
3.6.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

0 upvote

## Introduction

This blog will discuss a problem based on Arrays.  It involves a simple construction and implementation using array & loops.

## Problem Statement

Anuj has been given an array A[ ] of length N and an integer M. You have given Q queries in an array query[ ]. Your task is to find for each query the number of elements greater than or equal to query[i] and decrease all such elements by M. Process subsequent queries on updated array A[ ].

### INPUT

N = 4, Q = 3, and M = 1

A[] = [1, 2, 3, 4];

Query[] = [4, 3, 1];

1 2 4

### Explanation

For query[0]=4 : elements which are greater than or equal is {4}, and the modified array will be {1, 2, 3, 3}

For query[1]=3 : elements which are greater than or equal are {3, 3} and the modified array will be {1, 2, 2, 2}

For query[2]=1 : elements which are greater than or equal is {1, 2, 2, 2} and the modified array will be {0, 1, 1, 1}

### INPUT

N = 3, Q = 2, and M = 2

A[] = [1, 2, 3];

Query[] = [3, 3];

1 0

### Explanation

For query[0]=3 : elements which are greater than or equal is {3}, and the modified array will be {1, 2, 1}

For query[1]=3 : elements which are greater than or equal are {} and the modified array will be {1, 2, 1}

## 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[]

### 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!!

Live masterclass