Array range queries for elements with frequency same as value | Python 3 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
import math as mt NEW_LINE def solveQuery ( start , end , arr ) : NEW_LINE INDENT frequency = dict ( ) NEW_LINE for i in range ( start , end + 1 ) : NEW_LINE INDENT if arr [ i ] in frequency . keys ( ) : NEW_LINE INDENT frequency [ arr [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT frequency [ arr [ i ] ] = 1 NEW_LINE DEDENT DEDENT count = 0 NEW_LINE for x in frequency : NEW_LINE INDENT if x == frequency [ x ] : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT A = [ 1 , 2 , 2 , 3 , 3 , 3 ] NEW_LINE n = len ( A ) NEW_LINE queries = [ [ 0 , 1 ] , [ 1 , 1 ] , [ 0 , 2 ] , [ 1 , 3 ] , [ 3 , 5 ] , [ 0 , 5 ] ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT start = queries [ i ] [ 0 ] NEW_LINE end = queries [ i ] [ 1 ] NEW_LINE print ( " Answer ▁ for ▁ Query ▁ " , ( i + 1 ) , " ▁ = ▁ " , solveQuery ( start , end , A ) ) NEW_LINE DEDENT