Ways to form an array having integers in given range such that total sum is divisible by 2 | Function to return the number of ways to form an array of size n such that sum of all elements is divisible by 2 ; Represents first and last numbers of each type ( modulo 0 and 1 ) ; Count of numbers of each type between range ; Base Cases ; Ways to form array whose sum upto i numbers modulo 2 is 0 ; Ways to form array whose sum upto i numbers modulo 2 is 1 ; Return the required count of ways ; Driver Code
def countWays ( n , l , r ) : NEW_LINE INDENT tL , tR = l , r NEW_LINE L = [ 0 for i in range ( 2 ) ] NEW_LINE R = [ 0 for i in range ( 2 ) ] NEW_LINE L [ l % 2 ] = l NEW_LINE R [ r % 2 ] = r NEW_LINE l += 1 NEW_LINE r -= 1 NEW_LINE if ( l <= tR and r >= tL ) : NEW_LINE INDENT L [ l % 2 ] , R [ r % 2 ] = l , r NEW_LINE DEDENT cnt0 , cnt1 = 0 , 0 NEW_LINE if ( R [ 0 ] and L [ 0 ] ) : NEW_LINE INDENT cnt0 = ( R [ 0 ] - L [ 0 ] ) // 2 + 1 NEW_LINE DEDENT if ( R [ 1 ] and L [ 1 ] ) : NEW_LINE INDENT cnt1 = ( R [ 1 ] - L [ 1 ] ) // 2 + 1 NEW_LINE DEDENT dp = [ [ 0 for i in range ( 2 ) ] for i in range ( n + 1 ) ] NEW_LINE dp [ 1 ] [ 0 ] = cnt0 NEW_LINE dp [ 1 ] [ 1 ] = cnt1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = ( cnt0 * dp [ i - 1 ] [ 0 ] + cnt1 * dp [ i - 1 ] [ 1 ] ) NEW_LINE dp [ i ] [ 1 ] = ( cnt0 * dp [ i - 1 ] [ 1 ] + cnt1 * dp [ i - 1 ] [ 0 ] ) NEW_LINE DEDENT return dp [ n ] [ 0 ] NEW_LINE DEDENT n , l , r = 2 , 1 , 3 NEW_LINE print ( countWays ( n , l , r ) ) NEW_LINE