Number of ways to color N | JavaScript program for the above approach ; Function to count the ways to color block ; For storing powers of 2 ; For storing binomial coefficient values ; Calculating binomial coefficient using DP ; Calculating powers of 2 ; Sort the indices to calculate length of each section ; Initialise answer to 1 ; Find the length of each section ; Merge this section ; Return the final count ; Number of blocks ; Number of colored blocks ; Function call
let mod = 1000000007 ; function waysToColor ( arr , n , k ) { let powOf2 = new Array ( 500 ) ; let c = new Array ( 500 ) ; for ( let i = 0 ; i < 500 ; i ++ ) { c [ i ] = new Array ( 500 ) ; for ( let j = 0 ; j < 500 ; j ++ ) { c [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i <= n ; i ++ ) { c [ i ] [ 0 ] = 1 ; for ( let j = 1 ; j <= i ; j ++ ) { c [ i ] [ j ] = ( c [ i - 1 ] [ j ] + c [ i - 1 ] [ j - 1 ] ) % mod ; } } powOf2 [ 0 ] = powOf2 [ 1 ] = 1 ; for ( let i = 2 ; i <= n ; i ++ ) { powOf2 [ i ] = powOf2 [ i - 1 ] * 2 % mod ; } let rem = n - k ; arr [ k ++ ] = n + 1 ; arr . sort ( function ( a , b ) { return a - b ; } ) ; let answer = 1 ; for ( let i = 0 ; i < k ; i ++ ) { let x = arr [ i ] - ( i - 1 >= 0 ? arr [ i - 1 ] : 0 ) - 1 ; answer *= c [ rem ] [ x ] % mod * ( i != 0 && i != k - 1 ? powOf2 [ x ] : 1 ) % mod ; rem -= x ; } return answer ; } let N = 6 ; let K = 3 ; let arr = [ 1 , 2 , 6 , 0 ] ; document . write ( waysToColor ( arr , N , K ) ) ;