Find frequency of each element in a limited range array in less than O ( n ) time | C ++ program to count number of occurrences of each element in the 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 function
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; void findFrequencyUtil ( int arr [ ] , int low , int high , vector < int > & freq ) { if ( arr [ low ] == arr [ high ] ) { freq [ arr [ low ] ] += high - low + 1 ; } else { int mid = ( low + high ) / 2 ; findFrequencyUtil ( arr , low , mid , freq ) ; findFrequencyUtil ( arr , mid + 1 , high , freq ) ; } } void findFrequency ( int arr [ ] , int n ) { vector < int > freq ( arr [ n - 1 ] + 1 , 0 ) ; findFrequencyUtil ( arr , 0 , n - 1 , freq ) ; for ( int i = 0 ; i <= arr [ n - 1 ] ; i ++ ) if ( freq [ i ] != 0 ) cout << " Element ▁ " << i << " ▁ occurs ▁ " << freq [ i ] << " ▁ times " << endl ; } int main ( ) { int arr [ ] = { 1 , 1 , 1 , 2 , 3 , 3 , 5 , 5 , 8 , 8 , 8 , 9 , 9 , 10 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findFrequency ( arr , n ) ; return 0 ; }