Given an array arr[] of length N, the task is to find the minimum number of unique elements possible in total when the array is divided into K subsets (for all K in the range [1, N]) i.e. sum of count of unique elements present in each subset after dividing the given array into K subsets.
Examples:
Input: arr[] = { 2, 3, 3}
Output: {2, 2, 3}
Explanation:
K = 1: {2, 2, 3}
There are two distinct element in above array = {2, 3}
when array is divided into 1 subarrayK = 2: {2, 2}, { 3 }
There is one type of element in first array and for second subarray,
So the sum of count of unique is 1+1 = 2.
The array can also be divided into 2 subarrays as follows {2, 3}, {2} but then
the count of unique elements will be 2 and 1 and the sum will be 2+1 = 3 which is not the minimum.K = 3: {2}, {2}, {3}
Unique elements in first subarray = 1
Unique elements in second subarray = 1
Unique elements in third subarray = 1So total capabilities = 1+1+1 = 3
Input: arr[] = { 3, 1, 2, 2, 2, 4}
Output: {4, 4, 4, 4, 5, 6}
Explanation:
K = 1: {1, 2, 2, 2, 4, 3}
There are 4 type of elements = { 1, 2, 3, 4}
So for k = 1, required sum is = 4K = 2: {2, 2, 2, 4, 3}, {1}
There are 3 type of elements in first subarray = {2, 3, 4}
So unique elements in this subarray are 3
There is only one type of elements in second subarray = { 1}
So unique elements in this subarray is 1
So for k = 2, total minimum count = 3+1 = 4K = 3: {2, 2, 2, 3}, {1}, {4}
For k = 3, total minimum count = 2+1+1 = 4K = 4: {2, 2, 2}, {1}, {4}, {3}
For k = 4, total minimum count = 1+1+1+1 = 4K = 5: {2, 2}, {1}, {2}, {4}, {3}
For k = 5, total minimum count = 2+1+1+1+1 = 5K = 6: {1}, {2}, {2}, {2}, {4}, {3}
For k = 6, total minimum count = 1+1+1+1+1+1 = 6
Each subarray contains unique elements.
Approach: The problem can be solved on the basis of the following idea:
To minimize count of unique elements in each subset, group the elements with same values in one subset.
Refer the illustration below for a better understanding.
Illustration:
Consider array arr[] = {2, 2, 3}
Total number of unique elements = 2 (2 and 3)For dividing it in k = 1 parts:
=> There cannot be less than 2 unique elements in total.
=> Divide it into subsets {2, 2, 3}.
=> Total count of unique elements are 2For dividing it in k = 2 parts:
=> There cannot be less than 2 unique elements in total.
=> Divide it into subsets {2, 2} and {3}.
=> Total count of unique elements are 1 + 1 = 2For dividing it in k = 3 parts:
=> To minimize total count of unique elements break only one group of similar elements and keep the others intact.
=> Here there was only one group with all similar elements: {2, 2}.
=> Break that into 2 parts: {2}, {2}.
=> Divide it into subsets {2}, {2} and {3}.
=> Total count of unique elements are 1 + 1 + 1 = 3
Follow the steps mentioned below to implement the above idea:
- Calculate number of distinct elements using hashSet( let’s say count)
- Start iterating for k = 1 to N
- If k is at most count then try to group similar elements in one subarray to minimize the total count of unique elements. In this case, the total number of unique elements will always be equal to count as number of unique elements cannot be reduced.
- If k is greater than count then there will be minimum of k unique elements in total in all subsets, because we have to break one group of similar elements each time, which will increase the subarray and therefore the count of total unique elements also.
- Print the total count for each k,
Below implementation of the above approach.
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to count the // minimum possible number // of unique elements void solution( int a[], int n) { // To store the unique elements set< int > hs; for ( int i = 0; i < n; i++) hs.insert(a[i]); int cnt = hs.size(); for ( int i = 1; i <= n; i++) { if (i > hs.size()) { cnt++; cout << cnt << " " ; } else { cout << hs.size() << " " ; } } } // Driver Code int main() { int arr[] = { 2, 3, 3 }; int N = sizeof (arr) / sizeof (arr[0]); solution(arr, N); } // This code is contributed by Taranpreet |
Java
// Java implementation of above approach import java.io.*; import java.util.*; class GFG { // Function to count the // minimum possible number // of unique elements public static void solution( int [] a, int n) { // To store the unique elements HashSet<Integer> hs = new HashSet<>(); for ( int i : a) hs.add(i); int cnt = hs.size(); for ( int i = 1 ; i <= n; i++) { if (i > hs.size()) { cnt++; System.out.print(cnt + " " ); } else { System.out.print(hs.size() + " " ); } } } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 3 , 3 }; int N = arr.length; solution(arr, N); } } |
Python
# Python implementation of above approach # Function to count the # minimum possible number # of unique elements def solution(a, n): # To store the unique elements hs = set () for i in range ( 0 , n): hs.add(a[i]) cnt = len (hs) for i in range ( 1 , n + 1 ): if (i > len (hs)): cnt + = 1 print (cnt) else : print ( len (hs)) # Driver Code arr = [ 2 , 3 , 3 ] N = len (arr) solution(arr, N) # This code is contributed by Samim Hossain Mondal. |
C#
// C# implementation of above approach using System; using System.Collections.Generic; public class GFG{ // Function to count the // minimum possible number // of unique elements static void solution( int [] a, int n) { // To store the unique elements HashSet< int > hs = new HashSet< int >(); foreach ( int i in a) { hs.Add(i); } int cnt = hs.Count; for ( int i = 1; i <= n; i++) { if (i > hs.Count) { cnt++; Console.Write(cnt + " " ); } else { Console.Write(hs.Count + " " ); } } } // Driver Code static public void Main (){ int [] arr = { 2, 3, 3 }; int N = arr.Length; solution(arr, N); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach // Function to count the // minimum possible number // of unique elements function solution( a, n) { // To store the unique elements let hs = new Set(); for (let i of a) hs.add(i); let cnt = hs.size; for (let i = 1; i <= n; i++) { if (i > hs.size) { cnt++; document.write(cnt + " " ); } else { document.write(hs.size + " " ); } } } // Driver Code let arr = [ 2, 3, 3 ]; let N = arr.length; solution(arr, N); // This code is contributed by Potta Lokesh </script> |
2 2 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!