Количество пар, содержащих четные или последовательные элементы из данного массива

Опубликовано: 20 Сентября, 2022

Учитывая массив arr[] четного размера, задача состоит в том, чтобы найти количество пар после разделения arr[] на пары так, чтобы:

  • каждый элемент arr[] принадлежит ровно одной паре
  • оба они четные или
  • абсолютная разница между ними равна 1 , т.е. |X – Y| = 1 .

Примеры:

Input: arr[] = {11, 12, 16, 14}
Output: {11, 12}, {16, 14}
Explanation: arr[] can be partitioned into pairs in the following way. 
Pair 1 – {11, 12}, as |11-12| = 1. 
Pair 2 – {16, 14}, both 16 and 14 are even. 
Therefore, {11, 12} and {16, 14} are the two pairs. 

Input: A = {4, 7}
Output: No

Подход: эта проблема на основе наблюдения. Во-первых, если подсчет четных чисел и подсчет нечетных чисел не имеют одинаковой четности, то ответа не существует. Это означает, что если количество четных и нечетных чисел либо четное, либо оба нечетные. Теперь левый случай, когда четные числа и нечетные числа равны по частоте, то есть 2 случая:

  1. Вхождение четных и нечетных чисел четно, то ответ существует всегда.
  2. Вхождение четных и нечетных чисел является нечетным, затем проверьте, есть ли в массиве 2 числа, такие, что их абсолютная разница равна 1, и тогда появление четных и нечетных чисел становится, несмотря на это, ответ существует.

Выполните следующие шаги, чтобы решить данную проблему.

  • Создайте переменную even_count = 0 для подсчета четных чисел и odd_count = 0 для подсчета нечетных чисел.
  • Перебрать массив от index = 0 до n-1 , проверить, если arr[index]%2 == 0 , увеличить четный_счет , иначе увеличить нечетный_счет.
  • Проверьте, если четное_счетчик = нечетное_счетчик
    • если условие ложно, выведите Нет , так как пары массивов не могут существовать.
    • В противном случае проверьте, существуют ли в массиве 2 элемента, так что их абсолютная разница равна 1. Чтобы проверить, существует ли такая пара, создайте временный массив и сохраните количество каждого числа массива, затем выполните итерацию массива и проверьте, является ли последовательный элемент count больше 1 или нет.
    • Если существует, выведите Да .
  • Чтобы напечатать требуемые пары, выведите четные числа парами, затем нечетные числа парами и оставшиеся 2 элемента в качестве последней пары.

Ниже приведена реализация вышеуказанного подхода:

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ