Number of Binary Strings of length N with K adjacent Set Bits | JavaScript program to find the number of Bit Strings of length N with K adjacent set bits ; Function to find the number of Bit Strings of length N with K adjacent set bits ; Base Case when we form bit string of length n ; if f ( bit string ) = k , count this way ; Check if the last bit was set , if it was set then call for next index by incrementing the adjacent bit count else just call the next index with same value of adjacent bit count and either set the bit at current index or let it remain unset ; set the bit at currentIndex ; unset the bit at currentIndex ; Driver Code ; dp [ i ] [ j ] [ k ] represents bit strings of length i with f ( bit string ) = j and last bit as k ; initializes the dp ; total ways = ( ways by placing 1 st bit as 1 + ways by placing 1 st bit as 0 )
var MAX = 1000 ; function waysToKAdjacentSetBits ( dp , n , k , currentIndex , adjacentSetBits , lastBit ) { if ( currentIndex == n ) { if ( adjacentSetBits == k ) return 1 ; return 0 ; } if ( dp [ currentIndex ] [ adjacentSetBits ] [ lastBit ] != - 1 ) { return dp [ currentIndex ] [ adjacentSetBits ] [ lastBit ] ; } var noOfWays = 0 ; if ( lastBit == 1 ) { noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits + 1 , 1 ) ; noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits , 0 ) ; } else if ( ! lastBit ) { noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits , 1 ) ; noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits , 0 ) ; } dp [ currentIndex ] [ adjacentSetBits ] [ lastBit ] = noOfWays ; return noOfWays ; } var n = 5 , k = 2 ; var dp = Array . from ( Array ( MAX ) , ( ) => Array ( MAX ) ) ; for ( var i = 0 ; i < MAX ; i ++ ) for ( var j = 0 ; j < MAX ; j ++ ) dp [ i ] [ j ] = new Array ( 2 ) . fill ( - 1 ) ; var totalWays = waysToKAdjacentSetBits ( dp , n , k , 1 , 0 , 1 ) + waysToKAdjacentSetBits ( dp , n , k , 1 , 0 , 0 ) ; document . write ( " " + totalWays + " " ) ;