Find frequency of each element in a limited range array in less than O ( n ) time | A recursive function to count number of occurrences for each element in the array without traversing the whole array ; If element at index low is equal to element at index high in the array ; increment the frequency of the element by count of elements between high and low ; Find mid and recurse for left and right subarray ; A wrapper over recursive function findFrequencyUtil ( ) . It print number of occurrences of each element in the array . ; create a empty vector to store frequencies and initialize it by 0. Size of vector is maximum value ( which is last value in sorted array ) plus 1. ; Fill the vector with frequency ; Print the frequencies ; Driver Code
def findFrequencyUtil ( arr , low , high , freq ) : NEW_LINE INDENT if ( arr [ low ] == arr [ high ] ) : NEW_LINE INDENT freq [ arr [ low ] ] += high - low + 1 NEW_LINE DEDENT else : NEW_LINE INDENT mid = int ( ( low + high ) / 2 ) NEW_LINE findFrequencyUtil ( arr , low , mid , freq ) NEW_LINE findFrequencyUtil ( arr , mid + 1 , high , freq ) NEW_LINE DEDENT DEDENT def findFrequency ( arr , n ) : NEW_LINE INDENT freq = [ 0 for i in range ( n - 1 + 1 ) ] NEW_LINE findFrequencyUtil ( arr , 0 , n - 1 , freq ) NEW_LINE for i in range ( 0 , arr [ n - 1 ] + 1 , 1 ) : NEW_LINE INDENT if ( freq [ i ] != 0 ) : NEW_LINE INDENT print ( " Element " , i , " occurs " , freq [ i ] , " times " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 , 1 , 2 , 3 , 3 , 5 , 5 , 8 , 8 , 8 , 9 , 9 , 10 ] NEW_LINE n = len ( arr ) NEW_LINE findFrequency ( arr , n ) NEW_LINE DEDENT