Count of Numbers in Range where the number does not contain more than K non zero digits | Java 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
import java . util . * ; class Solution { static final int M = 20 ; static int dp [ ] [ ] [ ] = new int [ M ] [ M ] [ 2 ] ; static int K ; static Vector < Integer > num ; static int countInRangeUtil ( int pos , int cnt , int tight ) { if ( pos == num . size ( ) ) { 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 . get ( pos ) ) ; for ( int dig = 0 ; dig <= limit ; dig ++ ) { int currCnt = cnt ; if ( dig != 0 ) currCnt ++ ; int currTight = tight ; if ( dig < num . get ( pos ) ) currTight = 1 ; ans += countInRangeUtil ( pos + 1 , currCnt , currTight ) ; } return dp [ pos ] [ cnt ] [ tight ] = ans ; } static int countInRange ( int x ) { num = new Vector < Integer > ( ) ; while ( x != 0 ) { num . add ( x % 10 ) ; x /= 10 ; } Collections . reverse ( num ) ; 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 ( String args [ ] ) { int L = 1 , R = 1000 ; K = 3 ; System . out . println ( countInRange ( R ) - countInRange ( L - 1 ) ) ; L = 9995 ; R = 10005 ; K = 2 ; System . out . println ( countInRange ( R ) - countInRange ( L - 1 ) ) ; } }