Count of Numbers in Range where the number does not contain more than K non zero digits | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int M = 20 ; int dp [ M ] [ M ] [ 2 ] ; int K ; int countInRangeUtil ( int pos , int cnt , int tight , vector < int > num ) { 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 ? 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 , num ) ; } return dp [ pos ] [ cnt ] [ tight ] = ans ; } int countInRange ( int x ) { vector < int > num ; while ( x ) { num . push_back ( x % 10 ) ; x /= 10 ; } reverse ( num . begin ( ) , num . end ( ) ) ; memset ( dp , -1 , sizeof ( dp ) ) ; return countInRangeUtil ( 0 , 0 , 0 , num ) ; } int main ( ) { int L = 1 , R = 1000 ; K = 3 ; cout << countInRange ( R ) - countInRange ( L - 1 ) << endl ; L = 9995 , R = 10005 , K = 2 ; cout << countInRange ( R ) - countInRange ( L - 1 ) << endl ; return 0 ; }