Count Numbers Containing Given Digit K Times

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
DirectiOracleChegg Inc.

Problem statement

Ninja is in college and he is learning about numbers and counting he got an assignment in that and that task is hard for Ninja so he wants help from you. He has been provided with two numbers ‘L’ and ‘R’ which represent the range, Both numbers are inclusive. He has been provided with two more numbers which are ‘D’ and ‘K’ and now he has to do find the following :

What is the count of numbers in the range [L, R] in which each number has digit ‘D’ exactly ‘K’ times?

Example: 
Input: ‘L’ = 1, ‘R’ = 12, ‘D’ = 2, ‘K’ = 1 

Output: 2

As in the range, numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, and 2, 12 are the numbers where the digit ‘2’ comes exactly once.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains ‘L’ and ‘R’ the left and right boundaries of the range.
The second line contains ‘D’ the digit for which we have to check.
The third line contains 'K' the count of the digit 'D'.
Output format : 
For each test case, print the count of numbers satisfying the given criteria.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= L <= R <= 10^9
0 <= D <= 9
0 <= K <= 18

Time Limit: 1 sec
Sample Input 1 :
2
1 5
3
1
3 10
4
1
Sample Output 1 :
1
1
Explanation Of Sample Input 1 :
For the first case :
There is only one number 3 in the range [1, 5] is there whose digit count of 3 is 1 so the answer is 1.

For the second case :
There is only one number 4 in the range [3, 10] is there whose digit count of 4 is 1 so the answer is 1.
Sample Input 2 :
2
10 15
3 
1
1 20
5
0
Sample Output 2 :
1
18
Hint

Can you think about a straightforward solution?

Approaches (2)
Brute Force

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’.
Time Complexity

O( N ), Where ‘N’ denotes the range  R - L.  

 

We are looping in the range from  ‘L’ to ‘R’ so it will have a time complexity of O( R - L ) the helper function’s loop will run for at max 18 times for a number.

Hence the time complexity is O( N ).

Space Complexity

O( 1 ).
 

As we are using no extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Count Numbers Containing Given Digit K Times
Full screen
Console