Count number of ways to get Odd Sum | C ++ implementation ; Count the ways to sum up with odd by choosing one element form each pair ; Initialize two array with 0 ; if element is even ; store count of even number in i 'th pair ; if the element is odd ; store count of odd number in i 'th pair ; Initial state of dp array ; dp [ i ] [ 0 ] = total number of ways to get even sum upto i 'th pair ; dp [ i ] [ 1 ] = total number of ways to odd even sum upto i 'th pair ; dp [ n - 1 ] [ 1 ] = total number of ways to get odd sum upto n 'th pair ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int CountOfOddSum ( int a [ ] [ 2 ] , int n ) { int dp [ n ] [ 2 ] , cnt [ n ] [ 2 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < 2 ; j ++ ) { if ( a [ i ] [ j ] % 2 == 0 ) { cnt [ i ] [ 0 ] ++ ; } else { cnt [ i ] [ 1 ] ++ ; } } } dp [ 0 ] [ 0 ] = cnt [ 0 ] [ 0 ] , dp [ 0 ] [ 1 ] = cnt [ 0 ] [ 1 ] ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] * cnt [ i ] [ 0 ] + dp [ i - 1 ] [ 1 ] * cnt [ i ] [ 1 ] ) ; dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] * cnt [ i ] [ 1 ] + dp [ i - 1 ] [ 1 ] * cnt [ i ] [ 0 ] ) ; } return dp [ n - 1 ] [ 1 ] ; } int main ( ) { int a [ ] [ 2 ] = { { 1 , 2 } , { 3 , 6 } } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int ans = CountOfOddSum ( a , n ) ; cout << ans << " STRNEWLINE " ; return 0 ; }