Print all array elements appearing more than N / K times | C ++ program to implement the above approach ; Function to + find the upper_bound of an array element ; Stores minimum index in which K lies ; Stores maximum index in which K lies ; Calculate the upper bound of K ; Stores mid element of l and r ; If arr [ mid ] is less than or equal to K ; Right subarray ; Left subarray ; Function to print all array elements whose frequency is greater than N / K ; Sort the array arr [ ] ; Stores index of an array element ; Traverse the array ; Stores upper bound of arr [ i ] ; If frequency of arr [ i ] is greater than N / 4 ; Update i ; Driver Code ; Given array arr [ ] ; Size of array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int upperBound ( int arr [ ] , int N , int K ) { int l = 0 ; int r = N ; while ( l < r ) { int mid = ( l + r ) / 2 ; if ( arr [ mid ] <= K ) { l = mid + 1 ; } else { r = mid ; } } return l ; } void NDivKWithFreq ( int arr [ ] , int N , int K ) { sort ( arr , arr + N ) ; int i = 0 ; while ( i < N ) { int X = upperBound ( arr , N , arr [ i ] ) ; if ( ( X - i ) > N / 4 ) { cout << arr [ i ] << " ▁ " ; } i = X ; } } int main ( ) { int arr [ ] = { 1 , 2 , 2 , 6 , 6 , 6 , 6 , 7 , 10 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 4 ; NDivKWithFreq ( arr , N , K ) ; return 0 ; }