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

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

Примеры :

Input: arr[] = { 7, 5, 4, 9 }
Output: 6
Explanation: There are total 6 subarrays

1. { 4 }
2. { 5, 4 }
3. { 7, 5, 4 }
4. { 7, 5, 4, 9 }
5. { 5, 4, 9 }
6. { 4, 9 }

Input: arr[] = { 1, 3, 5 }
Output: 0

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

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

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

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

1. Общее количество подмассивов в массиве размера N равно N * (N + 1)/2 .
2. Количество подмассивов с нечетным произведением равно общему количеству непрерывных нечетных элементов, присутствующих в массиве.
3. Следовательно, количество подмассивов с четным произведением = (Общее количество подмассивов — Подмассивы с нечетным произведением) .
4. Выведите полученное значение количества подмассивов.

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

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