Самый длинный оставшийся массив различных элементов, возможный после многократного удаления максимальных и минимальных элементов триплетов.

Учитывая массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы многократно выбирать триплеты и удалять максимальные и минимальные элементы из троек в каждой операции так, чтобы оставшийся массив был максимально возможной длины и состоял только из различных элементов.

Примеры:

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

Подход: выполните следующие шаги, чтобы решить проблему:

• Пройдите массив arr[] и вычислите частоты каждого элемента массива.
• Для каждого отдельного элемента проверьте, является ли его частота четной или нечетной, и выполните следующие операции соответственно:
  • Если частота нечетная (кроме 1):
    • Удалите 2 элемента в каждой операции, выбрав одинаковые элементы в тройках. После серии операций останется только 1 вхождение элемента.
  • Если частота четная (кроме 2):
    • Удаляем по 2 элемента в каждой операции, выбирая одинаковые значения в триплетах. После ряда операций останется только два вхождения элемента
    • Теперь инициализируйте переменную, скажем, cnt , для хранения количества всех даже часто встречающихся элементов массива.
    • Если cnt четное, то сделать уникальными все четные элементы, не удаляя ни одного уникального элемента из массива, выбирая триплеты только из четных часто встречающихся элементов.
    • В противном случае удалите 1 уникальный элемент, чтобы сделать массив попарно различным.

Временная сложность: O(N)

Вспомогательное пространство: O(N)