Given two integers N and K and an array arr[] consisting of duplicate elements, the task is to split N elements into K sets of distinct elements.
Examples:
Input: N = 5, K = 2, arr[] = {3, 2, 1, 2, 3}
Output:
( 3 2 1 )
( 2 3 )
Input: N = 5, K = 2, arr[] = {2, 1, 1, 2, 1}
Output: -1
Explanation:
It is not possible to split all the elements into K sets of distinct elements as 1 appears more than K times in the array.
Approach: In order to solve the problem, we are using a map to store the frequency of every element. If the frequency of any element exceeds K, print -1. Maintain another map to store the sets for every respective frequencies. If no element has a frequency greater than K, print the sets for all corresponding frequencies as the required set.
Below is the implementation of the above approach:
C++
// C++ Program to split N elements// into exactly K sets consisting// of no distinct elements#include <bits/stdc++.h>using namespace std;// Function to check if possible to// split N elements into exactly K// sets consisting of no distinct elementsvoid splitSets(int a[], int n, int k){ // Store the frequency // of each element map<int, int> freq; // Store the required sets map<int, vector<int> > ans; for (int i = 0; i < n; i++) { // If frequency of a // particular element // exceeds K if (freq[a[i]] + 1 > k) { // Not possible cout << -1 << endl; return; } // Increase the frequency freq[a[i]] += 1; // Store the element for the // respective set ans[freq[a[i]]].push_back(a[i]); } // Display the sets for (auto it : ans) { cout << "( "; for (int i : it.second) { cout << i << " "; } cout << ")\n"; }}// Driver codeint main(){ int arr[] = { 2, 1, 2, 3, 1, 4, 1, 3, 1, 4 }; int n = sizeof(arr) / sizeof(int); int k = 4; splitSets(arr, n, k); return 0;} |
Java
// Java program to split N elements // into exactly K sets consisting // of no distinct elements import java.util.*;class GFG{ // Function to check if possible to// split N elements into exactly K// sets consisting of no distinct elementsstatic void splitSets(int a[], int n, int k){ // Store the frequency // of each element Map<Integer, Integer> freq = new HashMap<>(); // Store the required sets Map<Integer, ArrayList<Integer>> ans = new HashMap<>(); for(int i = 0; i < n; i++) { // If frequency of a // particular element // exceeds K if(freq.get(a[i]) != null) { if (freq.get(a[i]) + 1 > k) { // Not possible System.out.println(-1); return; } } // Increase the frequency freq.put(a[i], freq.getOrDefault(a[i], 0) + 1 ); // Store the element for the // respective set if( ans.get(freq.get(a[i])) == null) ans.put(freq.get(a[i]), new ArrayList<Integer>()); ans.get(freq.get(a[i])).add(a[i]); } // Display the sets for(ArrayList<Integer> it : ans.values()) { System.out.print("( "); for(int i = 0; i < it.size() - 1; i++) { System.out.print(it.get(i) + " "); } System.out.print(it.get(it.size() - 1)); System.out.println(" )"); }}// Driver code public static void main (String[] args){ int arr[] = { 2, 1, 2, 3, 1, 4, 1, 3, 1, 4 }; int n = arr.length; int k = 4; splitSets(arr, n, k);}}// This code is contributed by coder001 |
Python3
# Python3 Program to split N elements # into exactly K sets consisting # of no distinct elements # Function to check if possible to # split N elements into exactly K # sets consisting of no distinct elements def splitSets(a, n, k) : # Store the frequency # of each element freq = {} # Store the required sets ans = {} for i in range(n) : # If frequency of a # particular element # exceeds K if a[i] in freq : if freq[a[i]] + 1 > k : # Not possible print(-1) return # Increase the frequency if a[i] in freq : freq[a[i]] += 1 else : freq[a[i]] = 1 # Store the element for the # respective set if freq[a[i]] in ans : ans[freq[a[i]]].append(a[i]) else : ans[freq[a[i]]] = [a[i]] # Display the sets for it in ans : print("( ", end = "") for i in ans[it] : print(i , end = " ") print(")") arr = [ 2, 1, 2, 3, 1, 4, 1, 3, 1, 4 ] n = len(arr)k = 4splitSets(arr, n, k)# This code is contributed by divyesh072019 |
C#
// C# Program to split N elements// into exactly K sets consisting// of no distinct elementsusing System;using System.Collections.Generic;class GFG { // Function to check if possible to // split N elements into exactly K // sets consisting of no distinct elements static void splitSets(int[] a, int n, int k) { // Store the frequency // of each element Dictionary<int, int> freq = new Dictionary<int, int>(); // Store the required sets Dictionary<int, List<int>> ans = new Dictionary<int, List<int>>(); for (int i = 0; i < n; i++) { // If frequency of a // particular element // exceeds K if(freq.ContainsKey(a[i])) { if(freq[a[i]] + 1 > k) { // Not possible Console.WriteLine(-1); return; } } else if(1 > k) { // Not possible Console.WriteLine(-1); return; } // Increase the frequency if(freq.ContainsKey(a[i])) { freq[a[i]] += 1; } else { freq[a[i]] = 1; } // Store the element for the // respective set if(ans.ContainsKey(freq[a[i]])) { ans[freq[a[i]]].Add(a[i]); } else { ans[freq[a[i]]] = new List<int>(); ans[freq[a[i]]].Add(a[i]); } } // Display the sets foreach(KeyValuePair<int, List<int>> it in ans) { Console.Write("( "); foreach(int i in it.Value) { Console.Write(i + " "); } Console.WriteLine(")"); } } // Driver code static void Main() { int[] arr = { 2, 1, 2, 3, 1, 4, 1, 3, 1, 4 }; int n = arr.Length; int k = 4; splitSets(arr, n, k); }}// This code is contributed by divyeshrabadiya07 |
Javascript
// JS Program to split N elements// into exactly K sets consisting// of no distinct elements// Function to check if possible to// split N elements into exactly K// sets consisting of no distinct elementsfunction splitSets(a, n, k){ // Store the frequency // of each element let freq = {}; // Store the required sets let ans = {}; for (var i = 0; i < n; i++) { // If frequency of a // particular element // exceeds K if (freq[a[i]] + 1 > k) { // Not possible console.log (-1); return; } // Increase the frequency if (!freq.hasOwnProperty(a[i])) freq[a[i]] = 0 freq[a[i]] += 1; // Store the element for the // respective set if (!ans.hasOwnProperty(freq[a[i]])) ans[freq[a[i]]] = [] ans[freq[a[i]]].push(a[i]); } // Display the sets for (var [k, it] of Object.entries(ans)) { console.log("(", it.join(" "), ")") }}// Driver codelet arr = [ 2, 1, 2, 3, 1, 4, 1, 3, 1, 4 ];let n = arr.length;let k = 4;splitSets(arr, n, k);// This code is contributed by phasing17 |
Output:
( 2 1 3 4 ) ( 2 1 3 4 ) ( 1 ) ( 1 )
Time complexity: O(nlogn) since using a for loop
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!
