La array restante más larga posible de elementos distintos después de la eliminación repetida de elementos máximos y mínimos de tripletes

Dada una array arr[] que consta de N enteros, la tarea es seleccionar repetidamente tripletes y eliminar los elementos máximo y mínimo de los tripletes en cada operación, de modo que la array restante tenga la longitud más larga posible y consista solo en elementos distintos.

Ejemplos:

Entrada: N = 5, arr[] = {1, 2, 1, 3, 7}< 
Salida: 3 
Explicación: Seleccione el triplete (1, 2, 1) y elimine 1 y 2. La array restante es [1, 3, 7] en el que todos los elementos son distintos por pares.

Entrada: N = 6, arr[] = {8, 8, 8, 9, 9, 9} 
Salida: 2

Enfoque: siga los pasos a continuación para resolver el problema:
 

• Recorra la array arr[] y calcule las frecuencias de cada elemento de la array.
• Para cada elemento distinto, verifique si su frecuencia es par o impar y realice las siguientes operaciones en consecuencia:
  • Si la frecuencia es impar (excepto 1): 
    • Retire 2 elementos en cada operación, seleccionando los mismos elementos en tripletes. Después de una serie de operaciones, solo quedará 1 aparición del elemento.
  • Si la frecuencia es par (excepto 2): 
    • Eliminar 2 elementos en cada operación, seleccionando los mismos valores en tripletes. Después de una serie de operaciones, solo quedarán dos ocurrencias del elemento
    • Ahora, inicialice una variable, digamos cnt , para almacenar el recuento de todos los elementos de array incluso frecuentes.
    • Si cnt es par, haga que todos los elementos pares sean únicos, sin eliminar ningún elemento único de la array seleccionando trillizos solo de los elementos pares frecuentes.
    • De lo contrario, elimine 1 elemento único para que la array sea distinta por pares.

// 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 triplets
int 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 Code
int main()
{
    int N = 5;
    int A[] = { 1, 2, 1, 3, 7 };
    cout << maxUniqueElements(A, N);
}

// Java Program to implement
// the above approach
import 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 Program to implement
# the above approach
 
# Function to return length of longest
# remaining array of pairwise distinct
# array possible by removing triplets
def 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 Code
if __name__ == '__main__':
    N = 5
    A = [1, 2, 1, 3, 7]
    print(maxUniqueElements(A, N))
 
    # This code is contributed by SURENDRA_GANGWAR.

// C# Program to implement
// the above approach
using 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.

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to return length of longest
// remaining array of pairwise distinct
// array possible by removing triplets
function 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 Code
let N = 5;
let A = [ 1, 2, 1, 3, 7 ];
 
document.write(maxUniqueElements(A, N));
 
// This code is contributed by Potta Lokesh
 
</script>

3

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)