Array range queries for elements with frequency same as value | C ++ Program to answer Q queries to find number of times an element x appears x times in a Query subarray ; Returns the count of number x with frequency x in the subarray from start to end ; map for frequency of elements ; store frequency of each element in arr [ start ; end ] ; Count elements with same frequency as value ; Driver code ; 2D array of queries with 2 columns ; calculating number of queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solveQuery ( int start , int end , int arr [ ] ) { unordered_map < int , int > frequency ; for ( int i = start ; i <= end ; i ++ ) frequency [ arr [ i ] ] ++ ; int count = 0 ; for ( auto x : frequency ) if ( x . first == x . second ) count ++ ; return count ; } int main ( ) { int A [ ] = { 1 , 2 , 2 , 3 , 3 , 3 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int queries [ ] [ 3 ] = { { 0 , 1 } , { 1 , 1 } , { 0 , 2 } , { 1 , 3 } , { 3 , 5 } , { 0 , 5 } } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) { int start = queries [ i ] [ 0 ] ; int end = queries [ i ] [ 1 ] ; cout << " Answer ▁ for ▁ Query ▁ " << ( i + 1 ) << " ▁ = ▁ " << solveQuery ( start , end , A ) << endl ; } return 0 ; }