Максимизируйте количество пар соседних элементов с четной суммой, переставив массив
Учитывая массив 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.
- {arr[0](= 5), arr[1](= 5}, the sum of the elements is 10, which is even.
- {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}.
- {arr[0](= 9), arr[1](= 9}, the sum of the elements is 18, which is even.
- {arr[1](= 9), arr[2](= 3}, the sum of the elements is 12, which is even.
- {arr[2](= 3), arr[3](= 13}, the sum of the elements is 16, which is even.
- {arr[3](= 13), arr[4](= 13}, the sum of the elements is 26, which is even.
- {arr[4](= 13), arr[5](= 15}, the sum of the elements is 28, which is even.
- {arr[5](= 15), arr[6](= 16}, the sum of the elements is 31, which is not even.
- {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)
Эффективный подход. Описанный выше подход можно оптимизировать на основе следующих наблюдений:
- Известно, что:
- Нечетный + нечетный = четный
- Чет + Чет = Чет
- Чет + нечет = нечет
- Нечетный + четный = нечетный
- Общее количество соседних пар равно N-1.
- Следовательно, максимальное количество можно получить, сложив вместе все четные числа, а затем все нечетные числа или наоборот.
- При перестановке вышеописанным образом останется только одна пара соседних элементов с нечетной суммой, которая окажется на стыке четных и нечетных чисел.
Выполните следующие шаги, чтобы решить проблему:
- Найдите количество нечетных и четных чисел в массиве, а затем сохраните их в переменных, например, четных и нечетных .
- Если нечетные и четные оба больше 0, то в качестве ответа выведите общее количество N-2 .
- В противном случае выведите N-1 в качестве ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N), так как мы используем цикл для прохождения N раз.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.