Количество троек в массиве с нечетной суммой

Учитывая массив arr[] с N целыми числами, найдите количество троек i , j и k таких, что 1<= i < j < k <= N и arr[i] + arr[j] + arr[k] равно странный.

Пример:

Input: arr[] = {1, 2, 3, 4, 5}
Output: 4
Explanation: The given array contains 4 triplets with an odd sum. They are {1, 2, 4}, {1, 3, 5}, {2, 3, 4} and {2, 4, 5}.

Input: arr[] ={4, 5, 6, 4, 5, 10, 1, 7}
Output: 28

Наивный подход: данная проблема может быть решена путем перебора всех возможных неупорядоченных троек в массиве и отслеживания количества троек, сумма которых нечетна.
Временная сложность: O(N ³ )

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

• нечетный + четный + четный = нечетный
• нечетный + нечетный + нечетный = нечетный

Следовательно, для реализации вышеуказанной идеи мы можем подсчитать количество четных и нечетных целых чисел в массиве. Предположим, что количество нечетных целых чисел равно O , а количество четных целых чисел равно E. Таким образом, различные способы упорядочивания одного нечетного целого числа и двух четных целых чисел — это ^O C ₁ * ^E C ₂ -> (O * E * (E-1))/2 , а различные способы упорядочивания трех нечетных целых чисел — это ^O C ₃ — > (О * (О-1) * (О-2)) / 6 . Окончательный ответ будет суммой двух вышеуказанных значений.

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

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