Count Numbers Containing Given Digit K Times

In the naive approach, we will loop from ‘L to ‘R’ and for each number ‘I’ we will check if the count of ‘D’ in number ‘I’ is equal to the number ‘K’ then increase the answer and return that answer.

The steps are as follows:-

Function  countDigithelper(int i, int N, int K):

1. Create a variable called ‘ANS’ = 0.
2. Repeat while ‘i’>0
   • Increase answer by 1 if ‘i’%10 is equal to N.
   • Divide ‘i’ by 10.
3. Return 1 if ‘ANS’ is equal to ‘K’.
4. Else return 0.

Function countDigit(int L, int R, int N ,int K)

1. Initialize an int variable ‘COUNT’.
2. For each number ‘i’  from ‘L’ to ‘R’ inclusive
   • COUNT = COUNT+helper(I,N,K).
3. Return the value of ‘COUNT’.

In this approach, we will find solutions for ‘R’ and ‘L’-1 and then subtract the solution of ‘L’-1 from the solution of ‘R’ to get the answer for the range [L, R]. For each ‘num’ number from 1 to ‘X’ where ‘X’ will either be ‘R’ or ‘L’ - 1 we have to check if the count of the number ‘d’ in ‘num’ is equal to ‘k’ or not if it is ‘k’ then we have to increase our answer by 1.

e.g. for ‘X’ = 5, ‘d’ = 1, and ‘k’ = 1, We can see there is only one number in the range 1 to 5 is there where the count of digit 1 is equal to 1 and the number is 1 itself, But this process will give TLE as the value of ‘X’ is up to 10^9. 

So we will apply dynamic programming to it. We will check for each digit in the number what are the possibilities of number we can put at each digit so for a value of ‘X’ which is equal to 5000(assume). We have 4 places of digits ( _ _ _ _ ) where we have to check/put digits such that the resulting digit is less than or equal to 5000 also the requirement for the ‘d’ and ‘k’ is satisfied,

So initially, we have the range of 0 to 9 which we can put at each position but when we put a digit which makes our number greater than the range for example 5000 if we put 6 at first place and all the remaining digits equal to 000 then our number will be 6000>5000 so for checking what is the maximum digit we can put at the current place we will create a flag which will tell us in previous digit locations if we had put a digit which makes the number equal to respective range number for example if we put 5 at the first place of of number then later digits should be 0 else the number will get greater than 5000 so the range of the number is [0, 9] if the flag is high else set the value of limit to [0, current digit at the number ‘X’] after each digit value we have to set the value of flag to true if the current digit is the less then respective digit in ‘X’ else set it to false.

Also, we have to check the count of the digit ‘d’ in the number we are making because we have completed or put all the digits at all the positions then we will check the count of ‘d’ if it is equal to ‘k’ then increase answer by 1 now we have one special case if ‘d’ = 0 then we can not count leading zeros like 0004 into the count so for that we will put a ‘zFlag’ to check if there are no leading zeros to be counted.

 We will create a 4D- array named DP which will store the position of the digit, count of the digit ‘d’,  flag and zflag.

Handle the integer overflow.

The steps are as follows:-

countDigitHelper2( pos, currCount,  flag,  zFlag,  d, k,  digits[],  DP[][][][] )

1. Check if ‘pos’ is out of index of digits:
   • Check if ‘currCount’ is equal to ‘k’:-
     • Return 1.
   • Else return 0.
2. Check if (‘DP[pos][currCount][flag][zFlag]’) is already calculated earlier:-
   • Return ‘DP[pos][currCount][flag][zFlag]’.
3. Declare ‘ans’ = 0 to store the answer and ‘limit’ = 9 or ‘digits[pos]’ according to the ‘flag’ value.
4. For each ‘digit’ in range [0, limit+1]:
   • Declare ‘cnt’ = ‘currCnt’.
   • If the current ‘digit’ is equal to ‘D’:-
     • If ‘D’ is not equal to zero or if ‘D’ is zero and zFlag is high then the number is greater than 0:-
       • Increase count.
   • Declare ‘currf’ = ‘flag’.
   • If ‘digit’ is less than the current ‘digit’ limit then all next digits can go till 9.
   • Calculate the next digits of the number.
   • So ans += countDigitHelper2(pos+1,cnt,currf,(zFlag or digit!=0),n,k,digits,dp).
5. Set the value of DP and return.

countDigitHelper1( x, d, k )

1. Here ‘x’ is the limit of the upper bound, ‘D’ is the number that is to be counted in each number, ‘K’ is the total number of ‘D’ present in each number.
2. Create an array ‘DIGITS’ and push all digits of ‘X’ into it.
3. Created a 4-dimensional array ‘DP’ with size [20][20][2][2] and initialize it with -1.
4. Created another variable ‘ANS’ and initialize it with a helper( 0, 0, 0, 0, n, k, digits, DP ).
5. Return ‘ANS’.

countDigit(l, r, d, k)

1. Here ‘L’ is the lower limit, ‘R’ is the upper limit, ‘d’ is the digit on which we have to check and ‘K’ is the count of ‘d’ to be required in a number.
2. Return Solve( r, d, k ) - Solve( l-1, d, k ).