Количество соседних пар в заданном массиве с четной суммой

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

Пример:

Input: arr[] = {1, 12, 1, 3, 5}
Output:  1
Explanation: 1 pair can be formed with arr[3] and arr[4].

Input: arr[] = {1, 2, 3, 4, 5, 6,  8, 9}
Output: 0

Подход: Данную задачу можно решить с помощью жадного подхода. Можно заметить, что искомые пары могут быть образованы только из элементов, имеющих одинаковую четность, то есть либо (нечетный, нечетный), либо (четный, четный). Кроме того, количество пар, которые могут быть образованы из X последовательных нечетных или четных, равно полу (X / 2) . Следовательно, пройдите по заданному массиву и вычислите все возможные наборы последовательных целых чисел и добавьте (X / 2) для каждого набора в ответ.

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

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