Максимизируйте количество пар соседних элементов с четной суммой, переставив массив

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

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

Примеры:

Input: arr[] = {5, 5, 1}
Output: 2
Explanation:
The given array is already arranged to give the maximum count of adjacent pairs with an even sum.

  1. {arr[0](= 5), arr[1](= 5}, the sum of the elements is 10, which is even.
  2. {arr[1](= 5), arr[2](= 1}, the sum of the elements is 6, which is even.

Therefore, there are totals of 2 adjacent pairs with an even sum. And it is also the maximum possible count.

Input: arr[] = {9, 13, 15, 3, 16, 9, 13, 18}
Output: 6
Explanation:
One way to obtain the maximum count is to rearrange the array as {9, 9, 3, 13, 13, 15, 16, 18}.

  1. {arr[0](= 9), arr[1](= 9}, the sum of the elements is 18, which is even.
  2. {arr[1](= 9), arr[2](= 3}, the sum of the elements is 12, which is even.
  3. {arr[2](= 3), arr[3](= 13}, the sum of the elements is 16, which is even.
  4. {arr[3](= 13), arr[4](= 13}, the sum of the elements is 26, which is even.
  5. {arr[4](= 13), arr[5](= 15}, the sum of the elements is 28, which is even.
  6. {arr[5](= 15), arr[6](= 16}, the sum of the elements is 31, which is not even.
  7. {arr[6](= 16), arr[7](= 18}, the sum of the elements is 34, which is even.

Therefore, there are a total of 6 adjacent pairs with an even sum. And it is also the maximum possible count.

Наивный подход: самый простой подход — попробовать все возможные варианты расположения элементов, а затем подсчитать количество соседних пар с четной суммой.

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

Эффективный подход. Описанный выше подход можно оптимизировать на основе следующих наблюдений:

  1. Известно, что:
    • Нечетный + нечетный = четный
    • Чет + Чет = Чет
    • Чет + нечет = нечет
    • Нечетный + четный = нечетный
  2. Общее количество соседних пар равно N-1.
  3. Следовательно, максимальное количество можно получить, сложив вместе все четные числа, а затем все нечетные числа или наоборот.
  4. При перестановке вышеописанным образом останется только одна пара соседних элементов с нечетной суммой, которая окажется на стыке четных и нечетных чисел.

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

  • Найдите количество нечетных и четных чисел в массиве, а затем сохраните их в переменных, например, четных и нечетных .
  • Если нечетные и четные оба больше 0, то в качестве ответа выведите общее количество N-2 .
  • В противном случае выведите N-1 в качестве ответа.

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

Временная сложность: O(N), так как мы используем цикл для прохождения N раз.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.

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