Minimum number of distinct elements present in a K | C ++ program for the above approach ; Function to count the minimum number of distinct elements present in any subsequence of length K of the given array ; Stores the frequency of each array element ; Traverse the array ; Update frequency of array elements ; Store the required result ; Store the length of the required subsequence ; Store the frequencies in decreasing order ; Traverse the map ; Push the frequencies into the HashMap ; Sort the array in decreasing order ; Add the elements into the subsequence starting from one with highest frequency ; If length of subsequence is >= k ; Print the result ; Driver Code ; Store the size of the array ; Function Call to count minimum number of distinct elmeents present in a K - length subsequence
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findMinimumDistinct ( int A [ ] , int N , int K ) { unordered_map < int , int > mp ; for ( int i = 0 ; i < N ; i ++ ) mp [ A [ i ] ] ++ ; int count = 0 ; int len = 0 ; vector < int > counts ; for ( auto i : mp ) counts . push_back ( i . second ) ; sort ( counts . begin ( ) , counts . end ( ) , greater < int > ( ) ) ; for ( int i = 0 ; i < counts . size ( ) ; i ++ ) { if ( len >= K ) break ; len += counts [ i ] ; count ++ ; } cout << count ; } int main ( ) { int A [ ] = { 3 , 1 , 3 , 2 , 3 , 4 , 5 , 4 } ; int K = 4 ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; findMinimumDistinct ( A , N , K ) ; return 0 ; }