Count of N | Function to calculate count of ' N ' digit numbers such that bitwise AND of adjacent digits is 0. ; If digit = n + 1 , a valid n - digit number has been formed ; If the state has already been computed ; If current position is 1 , then any digit from [ 1 - 9 ] can be placed . If n = 1 , 0 can be also placed . ; For remaining positions , any digit from [ 0 - 9 ] can be placed after checking the conditions . ; Check if bitwise AND of current digit and previous digit is 0. ; Return answer ; Initialize dp array with - 1. ; Given Input ; Function call
function countOfNumbers ( digit , prev , n ) { if ( digit == n + 1 ) { return 1 ; } let val = dp [ digit ] [ prev ] ; if ( val != - 1 ) { return val ; } val = 0 ; if ( digit == 1 ) { for ( let i = ( n == 1 ? 0 : 1 ) ; i <= 9 ; ++ i ) { val += countOfNumbers ( digit + 1 , i , n ) ; } } else { for ( let i = 0 ; i <= 9 ; ++ i ) { if ( ( i & prev ) == 0 ) { val += countOfNumbers ( digit + 1 , i , n ) ; } } } return val ; } let dp = Array ( 100 ) . fill ( ) . map ( ( ) => Array ( 10 ) . fill ( - 1 ) ) ; let N = 3 ; document . write ( countOfNumbers ( 1 , 0 , N ) + " " ) ;