Count total number of N digit numbers such that the difference between sum of even and odd digits is 1 | A lookup table used for memoization . ; Memoization based recursive function to count numbers with even and odd digit sum difference as 1. This function considers leading zero as a digit ; Base Case ; If current subproblem is already computed ; Initialize result ; If current digit is odd , then add it to odd sum and recur ; else Add to even sum and recur ; Store current result in lookup table and return the same ; This is mainly a wrapper over countRec . It explicitly handles leading digit and calls countRec ( ) for remaining digits . ; Initialize number digits considered so far ; Initialize all entries of lookup table ; Initialize final answer ; Initialize even and odd sums ; Explicitly handle first digit and call recursive function countRec for remaining digits . Note that the first digit is considered as even digit . ; Driver program
let lookup = new Array ( 50 ) ; for ( let i = 0 ; i < 50 ; i ++ ) { lookup [ i ] = new Array ( 1000 ) ; for ( let j = 0 ; j < 1000 ; j ++ ) { lookup [ i ] [ j ] = new Array ( 1000 ) ; for ( let k = 0 ; k < 1000 ; k ++ ) { lookup [ i ] [ j ] [ k ] = new Array ( 2 ) ; } } } function countRec ( digits , esum , osum , isOdd , n ) { if ( digits == n ) return ( esum - osum == 1 ) ? 1 : 0 ; if ( lookup [ digits ] [ esum ] [ osum ] [ isOdd ] != - 1 ) return lookup [ digits ] [ esum ] [ osum ] [ isOdd ] ; let ans = 0 ; if ( isOdd == 1 ) for ( let i = 0 ; i <= 9 ; i ++ ) ans += countRec ( digits + 1 , esum , osum + i , 0 , n ) ; for ( let i = 0 ; i <= 9 ; i ++ ) ans += countRec ( digits + 1 , esum + i , osum , 1 , n ) ; return lookup [ digits ] [ esum ] [ osum ] [ isOdd ] = ans ; } function finalCount ( n ) { let digits = 0 ; for ( let i = 0 ; i < 50 ; i ++ ) for ( let j = 0 ; j < 1000 ; j ++ ) for ( let k = 0 ; k < 1000 ; k ++ ) for ( let l = 0 ; l < 2 ; l ++ ) lookup [ i ] [ j ] [ k ] [ l ] = - 1 ; let ans = 0 ; let esum = 0 , osum = 0 ; for ( let i = 1 ; i <= 9 ; i ++ ) ans += countRec ( digits + 1 , esum + i , osum , 1 , n ) ; return ans ; } let n = 3 ; document . write ( " " + n + " " + finalCount ( n ) ) ;