Count of Numbers in Range where the number does not contain more than K non zero digits | C # 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
using System ; using System . Collections . Generic ; class GFG { static int M = 20 ; static int [ , , ] dp = new int [ M , M , 2 ] ; static int K ; static List < int > num ; static int countInRangeUtil ( int pos , int cnt , int tight ) { if ( pos == num . Count ) { if ( cnt <= K ) return 1 ; return 0 ; } if ( dp [ pos , cnt , tight ] != - 1 ) return dp [ pos , cnt , tight ] ; int ans = 0 ; int limit = ( tight != 0 ? 9 : num [ pos ] ) ; for ( int dig = 0 ; dig <= limit ; dig ++ ) { int currCnt = cnt ; if ( dig != 0 ) currCnt ++ ; int currTight = tight ; if ( dig < num [ pos ] ) currTight = 1 ; ans += countInRangeUtil ( pos + 1 , currCnt , currTight ) ; } return dp [ pos , cnt , tight ] = ans ; } static int countInRange ( int x ) { num = new List < int > ( ) ; while ( x != 0 ) { num . Add ( x % 10 ) ; x /= 10 ; } num . Reverse ( ) ; for ( int i = 0 ; i < M ; i ++ ) for ( int j = 0 ; j < M ; j ++ ) for ( int k = 0 ; k < 2 ; k ++ ) dp [ i , j , k ] = - 1 ; return countInRangeUtil ( 0 , 0 , 0 ) ; } public static void Main ( ) { int L = 1 , R = 1000 ; K = 3 ; Console . WriteLine ( countInRange ( R ) - countInRange ( L - 1 ) ) ; L = 9995 ; R = 10005 ; K = 2 ; Console . WriteLine ( countInRange ( R ) - countInRange ( L - 1 ) ) ; } }