Count of all subsequences having adjacent elements with different parity | C # program implementation of the approach ; Function to find required subsequences ; dp [ i ] [ 0 ] : Stores the number of subsequences till i - th index ending with even element dp [ i ] [ 1 ] : Stores the number of subsequences till i - th index ending with odd element ; Initialise the dp [ ] [ ] with 0. ; If odd element is encountered ; Considering i - th element will be present in the subsequence ; Appending i - th element to all non - empty subsequences ending with even element till ( i - 1 ) th indexes ; Considering ith element will not be present in the subsequence ; Considering i - th element will be present in the subsequence ; Appending i - th element to all non - empty subsequences ending with odd element till ( i - 1 ) th indexes ; Considering ith element will not be present in the subsequence ; Count of all valid subsequences ; Driver code
using System ; class GFG { static int validsubsequences ( int [ ] arr , int n ) { long [ , ] dp = new long [ n + 1 , 2 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { dp [ i , 0 ] = 0 ; dp [ i , 1 ] = 0 ; } for ( int i = 1 ; i <= n ; i ++ ) { if ( arr [ i - 1 ] % 2 != 0 ) { dp [ i , 1 ] += 1 ; dp [ i , 1 ] += dp [ i - 1 , 0 ] ; dp [ i , 1 ] += dp [ i - 1 , 1 ] ; dp [ i , 0 ] += dp [ i - 1 , 0 ] ; } else { dp [ i , 0 ] += 1 ; dp [ i , 0 ] += dp [ i - 1 , 1 ] ; dp [ i , 0 ] += dp [ i - 1 , 0 ] ; dp [ i , 1 ] += dp [ i - 1 , 1 ] ; } } return ( int ) ( dp [ n , 0 ] + dp [ n , 1 ] ) ; } public static void Main ( ) { int [ ] arr = { 5 , 6 , 9 , 7 } ; int n = arr . Length ; Console . Write ( validsubsequences ( arr , n ) ) ; } }