Given an array arr[] consisting of N integers, the task is to repeatedly select triplets and remove the maximum and minimum elements from the triplets in each operation, such that the remaining array is of longest possible length and consists only of distinct elements.
Examples:
Input: N = 5, arr[] = {1, 2, 1, 3, 7}<
Output: 3
Explanation: Select the triplet (1, 2, 1) and remove 1 and 2. The remaining array is [1, 3, 7] in which all elements are pairwise distinct.Input: N = 6, arr[] = {8, 8, 8, 9, 9, 9}
Output: 2
Approach: Follow the steps below to solve the problem:
- Traverse the array arr[] and calculate the frequencies of each array element.
- For each distinct element, check if its frequency is even or odd and perform the following operations accordingly:
- If frequency is odd (Except 1):
- Remove 2 elements in each operation, by selecting same elements in triplets. After a series of operations, only 1 occurrence of the element will remain.
- If frequency is even (Except 2):
- Remove 2 elements in each operation, by selecting the same values in triplets. After a series of operations, only two occurrences of the element will remain
- Now, initialize a variable, say cnt, to store the count of all even frequent array elements.
- If cnt is even, then make all even elements unique, without removing any unique element from the array by selecting triplets only from even frequent elements.
- Otherwise, remove 1 unique element to make the array pairwise distinct.
- If frequency is odd (Except 1):
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to return length of longest// remaining array of pairwise distinct// array possible by removing tripletsint maxUniqueElements(int A[], int N){ // Stores the frequency of array elements unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { mp[A[i]]++; } // Iterate through the map int cnt = 0; for (auto x : mp) { // If frequency of current // element is even if (x.second % 2 == 0) { cnt++; } } // Stores the required count // of unique elements remaining int ans = mp.size(); // If count is odd if (cnt % 2 == 1) { ans--; } return ans;}// Driver Codeint main(){ int N = 5; int A[] = { 1, 2, 1, 3, 7 }; cout << maxUniqueElements(A, N);} |
Java
// Java Program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to return length of longest // remaining array of pairwise distinct // array possible by removing triplets static int maxUniqueElements(int[] Arr, int N) { // Stores the frequency of array elements HashMap<Integer, Integer> mp = new HashMap<>(); // Traverse the array for (int i = 0; i < N; i++) { if (mp.containsKey(Arr[i])) { mp.put(Arr[i], mp.get(Arr[i]) + 1); } else { mp.put(Arr[i], 1); } } // Iterate through the map int cnt = 0; for (Map.Entry<Integer, Integer> entry : mp.entrySet()) { // If frequency of current // element is even if ((entry.getValue()) % 2 == 0) { cnt++; } } // Stores the required count // of unique elements remaining int ans = mp.size(); // If count is odd if (cnt % 2 == 1) { ans--; } return ans; } // Driver Code public static void main(String[] args) { int N = 5; int A[] = { 1, 2, 1, 3, 7 }; System.out.println(maxUniqueElements(A, N)); }}// This code is contributed by maddler. |
Python3
# Python3 Program to implement# the above approach# Function to return length of longest# remaining array of pairwise distinct# array possible by removing tripletsdef maxUniqueElements(A, N): # Stores the frequency of array elements mp = {} # Traverse the array for i in range(N): if A[i] in mp: mp[A[i]] += 1 else: mp[A[i]] = 1 # Iterate through the map cnt = 0 for key,value in mp.items(): # If frequency of current # element is even if (value % 2 == 0): cnt += 1 # Stores the required count # of unique elements remaining ans = len(mp) # If count is odd if (cnt % 2 == 1): ans -= 1 return ans# Driver Codeif __name__ == '__main__': N = 5 A = [1, 2, 1, 3, 7] print(maxUniqueElements(A, N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;class GFG { // Function to return length of longest // remaining array of pairwise distinct // array possible by removing triplets static int maxUniqueElements(int[] Arr, int N) { // Stores the frequency of array elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < N; i++) { if (mp.ContainsKey(Arr[i])) { mp[Arr[i]] += 1; } else { mp[Arr[i]] = 1; } } // Iterate through the map int cnt = 0; foreach(KeyValuePair<int, int> entry in mp) { // If frequency of current // element is even if ((entry.Value) % 2 == 0) { cnt++; } } // Stores the required count // of unique elements remaining int ans = mp.Count; // If count is odd if (cnt % 2 == 1) { ans--; } return ans; } // Driver Code public static void Main(string[] args) { int N = 5; int[] A = { 1, 2, 1, 3, 7 }; Console.Write(maxUniqueElements(A, N)); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript program to implement// the above approach// Function to return length of longest// remaining array of pairwise distinct// array possible by removing tripletsfunction maxUniqueElements(A, N) { // Stores the frequency of array elements let mp = new Map(); // Traverse the array for(let i = 0; i < N; i++) { if (mp.has(A[i])) { mp.set(mp.get(A[i]), mp.get(A[i]) + 1); } else { mp.set(A[i], 1); } } // Iterate through the map let cnt = 0; for(let [key, value] of mp) { // If frequency of current // element is even if (value % 2 == 0) { cnt++; } } // Stores the required count // of unique elements remaining let ans = mp.size; // If count is odd if (cnt % 2 == 1) { ans--; } return ans;}// Driver Codelet N = 5;let A = [ 1, 2, 1, 3, 7 ];document.write(maxUniqueElements(A, N));// This code is contributed by Potta Lokesh</script> |
Output
3
Time Complexity: O(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!
