Count numbers with exactly K non | To store digits of N ; visited map ; DP Table ; Push all the digits of N into digits vector ; Function returns the count ; If desired number is formed whose sum is odd ; If it is not present in map , mark it as true and return 1 ; Sum is present in map already ; Desired result not found ; If that state is already calculated just return that state value ; Upper limit ; To store the count of desired numbers ; If k is non - zero , i ranges from 0 to j else [ 1 , j ] ; If current digit is 0 , decrement k and recurse sum is not changed as we are just adding 0 that makes no difference ; If i is non zero , then k remains unchanged and value is added to sum ; Memoize and return ; K is the number of exact non - zero elements to have in number ; break N into its digits ; We keep record of 0 s we need to place in the number
let digits = [ ] ; let vis = new Array ( 170 ) ; vis . fill ( false ) ; let dp = new Array ( 19 ) ; for ( let i = 0 ; i < 19 ; i ++ ) { dp [ i ] = new Array ( 19 ) ; for ( let j = 0 ; j < 19 ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = new Array ( 170 ) ; for ( let l = 0 ; l < 170 ; l ++ ) { dp [ i ] [ j ] [ k ] [ l ] = 0 ; } } } } function ConvertIntoDigit ( n ) { while ( n > 0 ) { let dig = n % 10 ; digits . push ( dig ) ; n = parseInt ( n / 10 , 10 ) ; } digits . reverse ( ) ; } function solve ( idx , k , tight , sum ) { if ( idx == digits . length && k == 0 && sum % 2 == 1 ) { if ( ! vis [ sum ] ) { vis [ sum ] = true ; return 1 ; } return 0 ; } if ( idx > digits . length ) { return 0 ; } if ( dp [ idx ] [ k ] [ tight ] [ sum ] > 0 ) { return dp [ idx ] [ k ] [ tight ] [ sum ] ; } let j ; if ( idx < digits . length && tight == 0 ) { j = digits [ idx ] ; } else { j = 9 ; } let cnt = 0 ; for ( let i = ( k > 0 ? 0 : 1 ) ; i <= j ; i ++ ) { let newtight = tight ; if ( i < j ) { newtight = 1 ; } if ( i == 0 ) cnt += solve ( idx + 1 , k - 1 , newtight , sum ) ; else cnt += solve ( idx + 1 , k , newtight , sum + i ) ; } dp [ idx ] [ k ] [ tight ] [ sum ] = cnt ; return dp [ idx ] [ k ] [ tight ] [ sum ] ; } let N , k ; N = 169 ; k = 2 ; ConvertIntoDigit ( N ) ; k = digits . length - k ; document . write ( solve ( 0 , k , 0 , 0 ) ) ;