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 = 4
Output: 2
Explanation: 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 = 5
Output: 2
Explanation: 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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the minimum number// of distinct elements present in any// subsequence of length K of the given arrayvoid findMinimumDistinct(int A[], int N, int K){ // Stores the frequency // of each array element unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) // Update frequency // of array elements mp[A[i]]++; // Store the required result int count = 0; // Store the length of the // required subsequence int len = 0; // Store the frequencies // in decreasing order vector<int> counts; // Traverse the map for (auto i : mp) // Push the frequencies // into the HashMap counts.push_back(i.second); // Sort the array in decreasing order sort(counts.begin(), counts.end(), greater<int>()); // Add the elements into the subsequence // starting from one with highest frequency for (int i = 0; i < counts.size(); i++) { // If length of subsequence is >= k if (len >= K) break; len += counts[i]; count++; } // Print the result cout << count;}// Driver Codeint main(){ int A[] = { 3, 1, 3, 2, 3, 4, 5, 4 }; int K = 4; // Store the size of the array int N = sizeof(A) / sizeof(A[0]); // Function Call to count minimum // number of distinct elements // present in a K-length subsequence findMinimumDistinct(A, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count the minimum number// of distinct elements present in any// subsequence of length K of the given arraystatic void findMinimumDistinct(int A[], int N, int K){ // Stores the frequency // of each array element Map<Integer, Integer> mp = new HashMap<>(); // Traverse the array for(int i = 0; i < N; i++) // Update frequency // of array elements mp.put(A[i], mp.getOrDefault(A[i], 0) + 1); // Store the required result int count = 0; // Store the length of the // required subsequence int len = 0; // Store the frequencies // in decreasing order ArrayList<Integer> counts = new ArrayList<>(); // Traverse the map for(Map.Entry<Integer, Integer> i : mp.entrySet()) // Push the frequencies // into the HashMap counts.add(i.getValue()); // Sort the array in decreasing order Collections.sort(counts, (a, b) -> b - a); // Add the elements into the subsequence // starting from one with highest frequency for(int i = 0; i < counts.size(); i++) { // If length of subsequence is >= k if (len >= K) break; len += counts.get(i); count++; } // Print the result System.out.print(count);}// Driver codepublic static void main(String[] args){ int A[] = { 3, 1, 3, 2, 3, 4, 5, 4 }; int K = 4; // Store the size of the array int N = A.length; // Function Call to count minimum // number of distinct elements // present in a K-length subsequence findMinimumDistinct(A, N, K);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approachfrom collections import Counter# Function to count the minimum number# of distinct elements present in any# subsequence of length K of the given arraydef findMinimumDistinct(A, N, K): # Stores the frequency # of each array element mp = Counter(A) # Store the required result count = 0 # Store the length of the # required subsequence length = 0 # Store the frequencies # in decreasing order counts = [] # Traverse the map for i in mp: # Push the frequencies # into the HashMap counts.append(mp[i]) # Sort the array in decreasing order counts = sorted(counts) counts.reverse() # Add the elements into the subsequence # starting from one with highest frequency for i in range(len(counts)): # If length of subsequence is >= k if (length >= K): break length += counts[i] count += 1 # Print the result print(count)# Driver CodeA = [3, 1, 3, 2, 3, 4, 5, 4]K = 4# Store the size of the arrayN = len(A)# Function Call to count minimum# number of distinct elements# present in a K-length subsequencefindMinimumDistinct(A, N, K)# This code is contributed by sudhanshugupta2019a |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class Program{ static void Main(string[] args) { int[] A = new int[] { 3, 1, 3, 2, 3, 4, 5, 4 }; int K = 4; int N = A.Length; Console.WriteLine(FindMinimumDistinct(A, N, K)); } static int FindMinimumDistinct(int[] A, int N, int K) { Dictionary<int, int> mp = new Dictionary<int, int>(); foreach (var item in A) { if (mp.ContainsKey(item)) mp[item]++; else mp[item] = 1; } int count = 0; int length = 0; List<int> counts = new List<int>(); foreach (var item in mp) counts.Add(item.Value); counts.Sort(); counts.Reverse(); for (int i = 0; i < counts.Count; i++) { if (length >= K) break; length += counts[i]; count++; } return count; }}// This code is contributed by shivamsharma215 |
Javascript
<script>// JavaScript program for the above approach// Function to count the minimum number// of distinct elements present in any// subsequence of length K of the given arrayfunction findMinimumDistinct(A, N, K){ // Stores the frequency // of each array element let mp = new Map(); // Traverse the array for (let i = 0; i < N; i++){ // Update frequency // of array elements if(mp.has(A[i])){ mp.set(A[i],mp.get(A[i])+1) } else mp.set(A[i],1) } // Store the required result let count = 0; // Store the length of the // required subsequence let len = 0; // Store the frequencies // in decreasing order let counts = []; // Traverse the map for (let [i,j] of mp) // Push the frequencies // into the HashMap counts.push(j); // Sort the array in decreasing order counts.sort((a,b)=>b-a); // Add the elements into the subsequence // starting from one with highest frequency for (let i = 0; i < counts.length; i++) { // If length of subsequence is >= k if (len >= K) break; len += counts[i]; count++; } // Print the result document.write(count);}// Driver Codelet A = [ 3, 1, 3, 2, 3, 4, 5, 4 ];let K = 4;// Store the size of the arraylet N = A.length;// Function Call to count minimum// number of distinct elements// present in a K-length subsequencefindMinimumDistinct(A, N, K);// This code is contributed by shinjanpatra</script> |
Output:
2
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
