Count of Numbers in Range where the number does not contain more than K non zero digits | Javascript Program to find the count of numbers in a range where the number does not contain more than K non zero digits ; states - position , count , tight ; K is the number of non zero digits ; This function returns the count of required numbers from 0 to num ; Last position ; If count of non zero digits is less than or equal to K ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 1 , means number has already become smaller so we can place any digit , otherwise num [ pos ] ; If the current digit is nonzero increment currCnt ; At this position , number becomes smaller ; Next recursive call ; This function converts a number into its digit vector and uses above function to compute the answer ; Initialize dp ; Driver Code to test above functions
let M = 20 ; let dp = new Array ( M ) ; for ( let i = 0 ; i < M ; i ++ ) { dp [ i ] = new Array ( M ) ; for ( let j = 0 ; j < M ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = 0 ; } } let K ; let num ; function countInRangeUtil ( pos , cnt , tight ) { if ( pos == num . length ) { if ( cnt <= K ) return 1 ; return 0 ; } if ( dp [ pos ] [ cnt ] [ tight ] != - 1 ) return dp [ pos ] [ cnt ] [ tight ] ; let ans = 0 ; let limit = ( tight != 0 ? 9 : num [ pos ] ) ; for ( let dig = 0 ; dig <= limit ; dig ++ ) { let currCnt = cnt ; if ( dig != 0 ) currCnt ++ ; let currTight = tight ; if ( dig < num [ pos ] ) currTight = 1 ; ans += countInRangeUtil ( pos + 1 , currCnt , currTight ) ; } return dp [ pos ] [ cnt ] [ tight ] = ans ; } function countInRange ( x ) { num = [ ] ; while ( x != 0 ) { num . push ( x % 10 ) ; x = Math . floor ( x / 10 ) ; } num . reverse ( ) ; for ( let i = 0 ; i < M ; i ++ ) for ( let j = 0 ; j < M ; j ++ ) for ( let k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; return countInRangeUtil ( 0 , 0 , 0 ) ; } let L = 1 , R = 1000 ; K = 3 ; document . write ( ( countInRange ( R ) - countInRange ( L - 1 ) ) + " " ) ; L = 9995 ; R = 10005 ; K = 2 ; document . write ( ( countInRange ( R ) - countInRange ( L - 1 ) ) + " " ) ;