Number of sub arrays with odd sum | C ++ program to find number of subarrays with odd sum ; Function to find number of subarrays with odd sum ; ' odd ' stores number of odd numbers upto ith index ' c _ odd ' stores number of odd sum subarrays starting at ith index ' Result ' stores the number of odd sum subarrays ; First find number of odd sum subarrays starting at 0 th index ; Find number of odd sum subarrays starting at ith index add to result ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countOddSum ( int a [ ] , int n ) { int odd = 0 , c_odd = 0 , result = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( a [ i ] & 1 ) { odd = ! odd ; } if ( odd ) { c_odd ++ ; } } for ( int i = 0 ; i < n ; i ++ ) { result += c_odd ; if ( a [ i ] & 1 ) { c_odd = ( n - i - c_odd ) ; } } return result ; } int main ( ) { int ar [ ] = { 5 , 4 , 4 , 5 , 1 , 3 } ; int n = sizeof ( ar ) / sizeof ( ar [ 0 ] ) ; cout << " The ▁ Number ▁ of ▁ Subarrays ▁ with ▁ odd ▁ sum ▁ is ▁ " << countOddSum ( ar , n ) ; return ( 0 ) ; }