# Minimum number of distinct elements present in a K-length subsequence in an array

Minimum number of distinct elements present in a K-length subsequence in an array

Given an array A[] consisting of N integers and an integer K, the task is to count the minimum number of distinct elements present in a subsequence of length K of the given array, A.

Examples:

Input: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 4Output: 2Explanation: The subsequence of length 4 containing minimum number of distinct elements is {3, 3, 3, 4}, consisting of 2 distinct elements, i.e. {3, 4}.

Input: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 5Output: 2Explanation: The subsequence of length 5 containing minimum number of distinct elements is {3, 3, 3, 4, 4}, consisting of 2 distinct elements, i.e. {3, 4}.

Naive Approach: The simplest approach is to generate all subsequences of length K and for each subsequence, find the number of distinct elements present in them. Finally, print the minimum number of distinct elements present.Time Complexity: O(K * NK)Auxiliary Space: O(N)

Efficient Approach: The above approach can be optimized using Hashing. Follow the steps below to solve the problem:Store the frequencies of all elements in the given array, A[] in a HashMap, say M.

Traverse the hashmap, M and push the frequencies in another array, say V.

Sort the array V in decreasing order.

Initialize two variables, cnt and len as 0, to store the required result and the length of the subsequence thus formed.

Traverse the array V[] using a variable, say i

If the value of len ≥ K, then break out of the loop.

Otherwise, increment the value of len by V[i] and cnt by 1.

After completing the above steps, print the value of cnt as the result.

Below is the implementation of the above approach:

C++

#include

using namespace std;

void findMinimumDistinct(int A[], int N, int K)

{

unordered_map mp;

for (int i = 0; i < N; i++)
mp[A[i]]++;
int count = 0;
int len = 0;
vector counts;
for (auto i : mp)
counts.push_back(i.second);
sort(counts.begin(), counts.end(),
greater());
for (int i = 0; i < counts.size(); i++) {
if (len >= K)

break;

len += counts[i];

count++;

}

cout