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
< ? php function countWays ( $ n , $ l , $ r ) { $ tL = $ l ; $ tR = $ r ; $ L = array_fill ( 0 , 2 , 0 ) ; $ R = array_fill ( 0 , 2 , 0 ) ; $ L [ $ l % 2 ] = $ l ; $ R [ $ r % 2 ] = $ r ; $ l ++ ; $ r -- ; if ( $ l <= $ tR && $ r >= $ tL ) { $ L [ $ l % 2 ] = $ l ; $ R [ $ r % 2 ] = $ r ; } $ cnt0 = 0 ; $ cnt1 = 0 ; if ( $ R [ 0 ] && $ L [ 0 ] ) $ cnt0 = ( $ R [ 0 ] - $ L [ 0 ] ) / 2 + 1 ; if ( $ R [ 1 ] && $ L [ 1 ] ) $ cnt1 = ( $ R [ 1 ] - $ L [ 1 ] ) / 2 + 1 ; $ dp = array ( ) ; $ dp [ 1 ] [ 0 ] = $ cnt0 ; $ dp [ 1 ] [ 1 ] = $ cnt1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { $ dp [ $ i ] [ 0 ] = ( $ cnt0 * $ dp [ $ i - 1 ] [ 0 ] + $ cnt1 * $ dp [ $ i - 1 ] [ 1 ] ) ; $ dp [ $ i ] [ 1 ] = ( $ cnt0 * $ dp [ $ i - 1 ] [ 1 ] + $ cnt1 * $ dp [ $ i - 1 ] [ 0 ] ) ; } return $ dp [ $ n ] [ 0 ] ; } $ n = 2 ; $ l = 1 ; $ r = 3 ; echo countWays ( $ n , $ l , $ r ) ; ? >