Given an array arr[] consisting of N integers, the task is to partition the array into two subsets such that the count of unique elements in both the subsets is the same and for each element, print 1 if that element belongs to the first subset. Otherwise, print 2. If it is not possible to do such a partition, then print “-1”.
Examples:
Input: arr[] = {1, 1, 2, 3, 4, 4}
Output: 1 1 1 2 1 1
Explanation: Consider the first and the second subset of the partition of the array as {1, 1, 2, 4 4} and {3}. Now, the above partition of subsets has equal count of distinct elements..Input: arr[] = {1, 1, 2, 2, 3}
Output: -1
Naive Approach: The given problem can be solved by generating all possible partition of the array elements into two subsets and if there exists any such partition whose count of distinct elements are the same, then print 1 and 2 according to the respective set array elements belongs to. Otherwise, print “-1” as there doesn’t exist any such possible partition of the array.
Time Complexity: O(N*2N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by finding the frequency of unique array elements if the frequency is odd, then there no such possible partition. Otherwise, print the partition of the subset accordingly. Follow the steps below to solve the problem:
- Initialize a Map, say M to store the frequency of all array elements.
- Initialize the array, say ans[] that stores the subset number where each array element belongs to.
- Find the count of the unique elements in the array by count the element having frequency 1 in the map M. Let this count be C.
- If the value of C is even, then move half of these elements into the first subset by marking those elements as 1 and rest all elements as 2 in the array ans[].
- Otherwise, check if there exist any element having a frequency greater than 2, then shift one instance of that element to the second subset. Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to partition the array into// two subsets such that count of unique// elements in both subsets is the samevoid arrayPartition(int a[], int n){ // Stores the subset number for // each array elements int ans[n]; // Stores the count of unique // array elements int cnt = 0; int ind, flag = 0; // Stores the frequency of elements map<int, int> mp; // Traverse the array for (int i = 0; i < n; i++) { mp[a[i]]++; } // Count of elements having a // frequency of 1 for (int i = 0; i < n; i++) { if (mp[a[i]] == 1) cnt++; // Check if there exists any // element with frequency > 2 if (mp[a[i]] > 2 && flag == 0) { flag = 1; ind = i; } } // Count of elements needed to // have frequency exactly 1 in // each subset int p = (cnt + 1) / 2; int ans1 = 0; // Initialize all values in the /// array ans[] as 1 for (int i = 0; i < n; i++) ans[i] = 1; // Traverse the array ans[] for (int i = 0; i < n; i++) { // This array element is a // part of first subset if (mp[a[i]] == 1 && ans1 < p) { ans[i] = 1; ans1++; } // Half array elements with // frequency 1 are part of // the second subset else if (mp[a[i]] == 1) { ans[i] = 2; } } // If count of elements is exactly // 1 are odd and has no element // with frequency > 2 if (cnt % 2 == 1 && flag == 0) { cout << -1 << endl; return; } // If count of elements that occurs // exactly once are even if (cnt % 2 == 0) { // Print the result for (int i = 0; i < n; i++) { cout << ans[i] << " "; } } // If the count of elements has // exactly 1 frequency are odd // and there is an element with // frequency greater than 2 else { // Print the result for (int i = 0; i < n; i++) { if (ind == i) cout << 2 << " "; else cout << ans[i] << " "; } }}// Driver Codeaint main(){ int arr[] = { 1, 1, 2, 3, 4, 4 }; int N = sizeof(arr) / sizeof(arr[0]); arrayPartition(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.HashMap;class GFG{// Function to partition the array into// two subsets such that count of unique// elements in both subsets is the samepublic static void arrayPartition(int a[], int n){ // Stores the subset number for // each array elements int[] ans = new int[n]; // Stores the count of unique // array elements int cnt = 0; int ind = 0, flag = 0; // Stores the frequency of elements HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array for (int i = 0; i < n; i++) { if(mp.containsKey(a[i])){ mp.put(a[i], mp.get(a[i]) + 1); }else{ mp.put(a[i], 1); } } // Count of elements having a // frequency of 1 for (int i = 0; i < n; i++) { if (mp.get(a[i]) == 1) cnt++; // Check if there exists any // element with frequency > 2 if (mp.get(a[i]) > 2 && flag == 0) { flag = 1; ind = i; } } // Count of elements needed to // have frequency exactly 1 in // each subset int p = (cnt + 1) / 2; int ans1 = 0; // Initialize all values in the /// array ans[] as 1 for (int i = 0; i < n; i++) ans[i] = 1; // Traverse the array ans[] for (int i = 0; i < n; i++) { // This array element is a // part of first subset if (mp.get(a[i]) == 1 && ans1 < p) { ans[i] = 1; ans1++; } // Half array elements with // frequency 1 are part of // the second subset else if (mp.get(a[i]) == 1) { ans[i] = 2; } } // If count of elements is exactly // 1 are odd and has no element // with frequency > 2 if (cnt % 2 == 1 && flag == 0) { System.out.println(-1 + "\n"); return; } // If count of elements that occurs // exactly once are even if (cnt % 2 == 0) { // Print the result for (int i = 0; i < n; i++) { System.out.print(ans[i] + " "); } } // If the count of elements has // exactly 1 frequency are odd // and there is an element with // frequency greater than 2 else { // Print the result for (int i = 0; i < n; i++) { if (ind == i) System.out.print(2 + " "); else System.out.print(ans[i] + " "); } }}// Driver Codeapublic static void main(String args[]){ int arr[] = { 1, 1, 2, 3, 4, 4 }; int N = arr.length; arrayPartition(arr, N);}}// This code is contributed by gfgking. |
Python3
# Python3 program for the above approach# Function to partition the array into# two subsets such that count of unique# elements in both subsets is the samedef arrayPartition(a, n): # Stores the subset number for # each array elements ans = [0] * n # Stores the count of unique # array elements cnt = 0 ind, flag = 0, 0 # Stores the frequency of elements mp = {} # Traverse the array for i in a: mp[i] = mp.get(i, 0) + 1 # Count of elements having a # frequency of 1 for i in range(n): if ((a[i] in mp) and mp[a[i]] == 1): cnt += 1 # Check if there exists any # element with frequency > 2 if (mp[a[i]] > 2 and flag == 0): flag = 1 ind = i # Count of elements needed to # have frequency exactly 1 in # each subset p = (cnt + 1) // 2 ans1 = 0 # Initialize all values in the # array ans[] as 1 for i in range(n): ans[i] = 1 # Traverse the array ans[] for i in range(n): # This array element is a # part of first subset if ((a[i] in mp) and mp[a[i]] == 1 and ans1 < p): ans[i] = 1 ans1 += 1 # Half array elements with # frequency 1 are part of # the second subset elif ((a[i] in mp) and mp[a[i]] == 1): ans[i] = 2 # If count of elements is exactly # 1 are odd and has no element # with frequency > 2 if (cnt % 2 == 1 and flag == 0): print (-1) return # If count of elements that occurs # exactly once are even if (cnt % 2 == 0): # Print the result print(*ans) # If the count of elements has # exactly 1 frequency are odd # and there is an element with # frequency greater than 2 else: # Print the result for i in range(n): if (ind == i): print(2, end = " ") else: print(ans[i], end = " ")# Driver Codeaif __name__ == '__main__': arr = [ 1, 1, 2, 3, 4, 4 ] N = len(arr) arrayPartition(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to partition the array into// two subsets such that count of unique// elements in both subsets is the samestatic void arrayPartition(int []a, int n){ // Stores the subset number for // each array elements int []ans = new int[n]; // Stores the count of unique // array elements int cnt = 0; int ind=0, flag = 0; // Stores the frequency of elements Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse the array for (int i = 0; i < n; i++) { if(mp.ContainsKey(a[i])) mp[a[i]]++; else mp.Add(a[i],1); } // Count of elements having a // frequency of 1 for (int i = 0; i < n; i++) { if (mp.ContainsKey(a[i]) && mp[a[i]] == 1) cnt++; // Check if there exists any // element with frequency > 2 if (mp.ContainsKey(a[i]) && mp[a[i]] > 2 && flag == 0) { flag = 1; ind = i; } } // Count of elements needed to // have frequency exactly 1 in // each subset int p = (cnt + 1) / 2; int ans1 = 0; // Initialize all values in the /// array ans[] as 1 for (int i = 0; i < n; i++) ans[i] = 1; // Traverse the array ans[] for (int i = 0; i < n; i++) { // This array element is a // part of first subset if (mp.ContainsKey(a[i]) && mp[a[i]] == 1 && ans1 < p) { ans[i] = 1; ans1++; } // Half array elements with // frequency 1 are part of // the second subset else if (mp.ContainsKey(a[i]) && mp[a[i]] == 1) { ans[i] = 2; } } // If count of elements is exactly // 1 are odd and has no element // with frequency > 2 if (cnt % 2 == 1 && flag == 0) { Console.Write(-1); return; } // If count of elements that occurs // exactly once are even if (cnt % 2 == 0) { // Print the result for (int i = 0; i < n; i++) { Console.Write(ans[i] + " "); } } // If the count of elements has // exactly 1 frequency are odd // and there is an element with // frequency greater than 2 else { // Print the result for (int i = 0; i < n; i++) { if (ind == i) Console.Write(2 + " "); else Console.Write(ans[i] + " "); } }}// Driver Codeapublic static void Main(){ int []arr = { 1, 1, 2, 3, 4, 4 }; int N = arr.Length; arrayPartition(arr, N);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// JavaScript program for the above approach// Function to partition the array into// two subsets such that count of unique// elements in both subsets is the samefunction arrayPartition(a, n) { // Stores the subset number for // each array elements let ans = new Array(n); // Stores the count of unique // array elements let cnt = 0; let ind, flag = 0; // Stores the frequency of elements let mp = new Map(); // Traverse the array for (let i = 0; i < n; i++) { if (mp.has(a[i])) { mp.set(a[i], mp.get(a[i]) + 1) } else { mp.set(a[i], 1) } } // Count of elements having a // frequency of 1 for (let i = 0; i < n; i++) { if (mp.get(a[i]) == 1) cnt++; // Check if there exists any // element with frequency > 2 if (mp.get(a[i]) > 2 && flag == 0) { flag = 1; ind = i; } } // Count of elements needed to // have frequency exactly 1 in // each subset let p = Math.floor((cnt + 1) / 2); let ans1 = 0; // Initialize all values in the /// array ans[] as 1 for (let i = 0; i < n; i++) ans[i] = 1; // Traverse the array ans[] for (let i = 0; i < n; i++) { // This array element is a // part of first subset if (mp.get(a[i]) == 1 && ans1 < p) { ans[i] = 1; ans1++; } // Half array elements with // frequency 1 are part of // the second subset else if (mp.get(a[i]) == 1) { ans[i] = 2; } } // If count of elements is exactly // 1 are odd and has no element // with frequency > 2 if (cnt % 2 == 1 && flag == 0) { document.write(-1 + "<br>"); return; } // If count of elements that occurs // exactly once are even if (cnt % 2 == 0) { // Print the result for (let i = 0; i < n; i++) { document.write(ans[i] + " "); } } // If the count of elements has // exactly 1 frequency are odd // and there is an element with // frequency greater than 2 else { // Print the result for (let i = 0; i < n; i++) { if (ind == i) document.write(2 + " "); else document.write(ans[i] << " "); } }}// Driver Codealet arr = [1, 1, 2, 3, 4, 4];let N = arr.lengtharrayPartition(arr, N);</script> |
Output:
1 1 1 2 1 1
Time Complexity: O(NlogN)
Auxiliary Space: O(N) as using extra space for Map
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!
