human
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"
Solution in Python:
assistant
#Here is code to find frequency of each element in a limited range array in less than O ( n ) time and the other steps required.
 def findFrequencyUtil ( arr , low , high , freq ) :
	if ( arr [ low ] == arr [ high ] ) :
		freq [ arr [ low ] ] += high - low + 1
	else :
		mid = int ( ( low + high ) / 2 )
		findFrequencyUtil ( arr , low , mid , freq )
		findFrequencyUtil ( arr , mid + 1 , high , freq )
def findFrequency ( arr , n ) :
	freq = [ 0 for i in range ( n - 1 + 1 ) ]
	findFrequencyUtil ( arr , 0 , n - 1 , freq )
	for i in range ( 0 , arr [ n - 1 ] + 1 , 1 ) :
		if ( freq [ i ] != 0 ) :
			print ( " Element " , i , " occurs " , freq [ i ] , " times " )
if __name__ == ' _ _ main _ _ ' :
	arr = [ 1 , 1 , 1 , 2 , 3 , 3 , 5 , 5 , 8 , 8 , 8 , 9 , 9 , 10 ]
	n = len ( arr )
	findFrequency ( arr , n )