Approach
For each query, the naive approach to solve the above problem is to traverse the whole subarray and count the frequency of each element. If the frequency of an element in the subarray is equal to the number itself, then consider it in the final answer; otherwise, leave it.
The algorithm of the approach is described below.
Algorithm
-
Create a function getCount():
-
Function Description:
- It takes array ‘ARR’, ‘L’ and ‘R’ as an input.
-
It returns the count of all such numbers in the subarray(starting from the Lth index and ending on the Rth index) whose frequency is equal to the number itself.
-
Function Working:
- Create a variable ‘ANS’ to store the total count. Initialize ANS = 0.
- Create a map to store the frequency of elements.
-
Iterate loop in the subarray and do the following in each traversal:
-
Iterate map and check if the key and value are equal then:
-
Return ANS.
- Call the above function for all the queries.
Program
#include <bits/stdc++.h>
using namespace std;
/*Function to get the count.*/
int getCount(vector<int> &arr, int l, int r)
{
/*Variable to store the total count.*/
int ans = 0;
/*Map to store the frequency of elements.*/
unordered_map<int, int> mp;
for (int i = l; i <= r; i++)
{
mp[arr[i]]++;
}
for (auto it : mp)
{
/*Check if the frequency of the element is equal to the number itself.*/
if (it.first == it.second)
ans++;
}
return ans;
}
int main()
{
/*Taking the array as an input.*/
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
/*taking the number of queries as an input.*/
int q;
cin >> q;
while (q--)
{
int l, r;
cin >> l >> r;
/*Function call.*/
int ans = getCount(arr, l, r);
cout << ans << endl;
}
return 0;
}
Input
7
3 1 2 2 3 3 7
2
0 6
2 3
Output
3
1
Time Complexity
O(Q * N), where ‘N’ is the number of elements in the array, and ‘Q’ is the total number of queries.
Reason: Storing the frequency of each element takes O(N) time, and we need to perform this for all the queries. Hence, its time complexity is O(Q * N).
Space Complexity
O(N), where N is the number of elements in the array.
Reason: Creating a map takes O(N) space in the worst case.
FAQs
-
What is a map?
The map is a data structure that stores data in key-value pairs. The map is of two types, i.e., ordered and unordered maps.
-
What is the difference between ordered and unordered maps?
The ordered map uses the concept of the red-black tree for its implementation, while the unordered map uses the concept of hashing.
-
What is the time complexity of the above code if we use an ordered map?
If we use an ordered map instead of an unordered map, its time complexity is O(N * Q *log(Q)). As insertion takes log(N) time in the ordered map and O(1) time in the unordered map.
-
How can we calculate the frequency of elements?
We can calculate the frequency of an element in the subarray by creating a map data structure and storing the number and its frequency as key-value pairs.
-
Can we solve the above problem in O(1) extra space?
Yes, we can, but time complexity increases in that implementation, as we need to traverse the whole array for all the elements.
Key Takeaways
In this blog, we learned about an interesting problem based on a range query. We solved the problem using the brute force approach. Another problem involving range query is: here.
Hence learning never stops, and there is a lot more to learn.
Check out this problem - Longest Subarray With Sum K
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 Coding!
38+ registered 