Count of all subsequences having adjacent elements with different parity | C ++ Program to implement the above 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int validsubsequences ( int arr [ ] , int n ) { long long int dp [ 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 ) { 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 dp [ n ] [ 0 ] + dp [ n ] [ 1 ] ; } int main ( ) { int arr [ ] = { 5 , 6 , 9 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << validsubsequences ( arr , n ) ; return 0 ; }