Count number of ways to get Odd Sum | 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
def CountOfOddSum ( a , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 2 ) ] for i in range ( n ) ] NEW_LINE cnt = [ [ 0 for i in range ( 2 ) ] for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( 2 ) : NEW_LINE INDENT if ( a [ i ] [ j ] % 2 == 0 ) : NEW_LINE INDENT cnt [ i ] [ 0 ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ i ] [ 1 ] += 1 NEW_LINE DEDENT DEDENT DEDENT dp [ 0 ] [ 0 ] = cnt [ 0 ] [ 0 ] NEW_LINE dp [ 0 ] [ 1 ] = cnt [ 0 ] [ 1 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] * cnt [ i ] [ 0 ] + dp [ i - 1 ] [ 1 ] * cnt [ i ] [ 1 ] ) NEW_LINE dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] * cnt [ i ] [ 1 ] + dp [ i - 1 ] [ 1 ] * cnt [ i ] [ 0 ] ) NEW_LINE DEDENT return dp [ n - 1 ] [ 1 ] NEW_LINE DEDENT a = [ [ 1 , 2 ] , [ 3 , 6 ] ] NEW_LINE n = len ( a ) NEW_LINE ans = CountOfOddSum ( a , n ) NEW_LINE print ( ans ) NEW_LINE