Count number of ways to get Odd Sum | C # implementation of above approach ; 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
using System ; class GFG { static int CountOfOddSum ( int [ , ] a , int n ) { int [ , ] dp = new int [ n , 2 ] ; int [ , ] cnt = new int [ n , 2 ] ; 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 ] ; } public static void Main ( ) { int [ , ] a = { { 1 , 2 } , { 3 , 6 } } ; int n = a . GetLength ( 1 ) ; int ans = CountOfOddSum ( a , n ) ; Console . WriteLine ( ans ) ; } }