Minimum replacements required to have at most K distinct elements in the array | Java program to implement the above approach ; Function to find minimum count of array elements required to be replaced such that count of distinct elements is at most K ; Store the frequency of each distinct element of the array ; Traverse the array ; Update frequency of arr [ i ] ; Store frequency of each distinct element of the array ; Traverse the map ; Stores key of the map ; Insert mp [ i ] into Freq [ ] ; Sort Freq [ ] in descending order ; Stores size of Freq [ ] ; If len is less than or equal to K ; Stores minimum count of array elements required to be replaced such that count of distinct elements is at most K ; Iterate over the range [ K , len ] ; Update cntMin ; Driver Code
import java . util . * ; class GFG { static int min_elements ( int arr [ ] , int N , int K ) { HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( mp . containsKey ( arr [ i ] ) ) { mp . put ( arr [ i ] , mp . get ( arr [ i ] ) + 1 ) ; } else { mp . put ( arr [ i ] , 1 ) ; } } Vector < Integer > Freq = new Vector < Integer > ( ) ; for ( Map . Entry < Integer , Integer > it : mp . entrySet ( ) ) { int i = it . getKey ( ) ; Freq . add ( mp . get ( i ) ) ; } Collections . sort ( Freq , Collections . reverseOrder ( ) ) ; int len = Freq . size ( ) ; if ( len <= K ) { return 0 ; } int cntMin = 0 ; for ( int i = K ; i < len ; i ++ ) { cntMin += Freq . get ( i ) ; } return cntMin ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 1 , 3 , 2 , 4 , 1 , 1 , 2 , 3 , 4 } ; int N = arr . length ; int K = 3 ; System . out . print ( min_elements ( arr , N , K ) ) ; } }