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
function findFrequencyUtil ( arr , low , high , freq ) { if ( arr [ low ] == arr [ high ] ) { freq [ arr [ low ] ] += high - low + 1 ; } else { let mid = Math . floor ( ( low + high ) / 2 ) ; findFrequencyUtil ( arr , low , mid , freq ) ; findFrequencyUtil ( arr , mid + 1 , high , freq ) ; } } function findFrequency ( arr , n ) { let freq = new Array ( arr [ n - 1 ] + 1 ) ; for ( let i = 0 ; i < arr [ n - 1 ] + 1 ; i ++ ) { freq [ i ] = 0 ; } findFrequencyUtil ( arr , 0 , n - 1 , freq ) ; for ( let i = 0 ; i <= arr [ n - 1 ] ; i ++ ) if ( freq [ i ] != 0 ) document . write ( " " + i + " " + freq [ i ] + " " ) ; } let arr = [ 1 , 1 , 1 , 2 , 3 , 3 , 5 , 5 , 8 , 8 , 8 , 9 , 9 , 10 ] ; let n = arr . length ; findFrequency ( arr , n ) ;