Digit Count In Range

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
16 upvotes
Asked in companies
MicrosofteBayOla

Problem statement

You are given an integer ‘K’, and two numbers ‘A’ and ‘B’. You need to count the occurrences of the given digit ‘K’, in the range [A, B].

Note: 
 You need to count occurrences at every place of the number. You also need to include the lower and higher limits of the given range
For example : 
Given K = 3, A = 1, B = 15, then 3 occurs 2 times(3, 13) in the range [1, 15], so you need to print 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains a single integer ‘K’, denoting the digit of which you need to count the occurrences.

The second line of each test case contains two space-separated integers, ‘A’ and ‘B’, denoting the lower and higher limits of the range in which you need to count the occurrence.
Output Format: 
For each test case, you need to print a single integer that denotes occurrences of ‘K’ in the range [A, B].

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 100
0 <= K <= 9
0 <= A, B <= 10^18

where ‘T’ is the number of test cases, ‘K’ is the digit and ‘A’ and ‘B’ are the two integers.

Time limit: 1 sec
Sample Input 1:
2
3
1 15
2
2 12
Sample Output 1:
2
2
Explanation of sample input 1:
In the first test case, 
Number of occurrences of 3 in range [1, 13] = 2 (3, 13). Return 2


In the second test case, 
Number of occurrences of 2 in range [2, 12] = 2 (2, 12). Return 2
Sample Input 2:
2
1 
1 15
3
3 33
Sample Output 2:
8
8
Explanation of sample input 1:
In the first test case, 
Number of occurrences of 1 in range [1, 15] = 8 (1, 10, 11, 12, 13, 14, 15). Return 8

In the second test case, 
Number of occurrences of 3 in range [3, 33] = 8 (3, 13, 23, 30, 31, 32, 33). Return 8
Hint

Can you think of iterating through all numbers of the range?

Approaches (2)
Brute Force

A basic approach will be to simply iterate through the given range and keep a count of the occurrences of the given digit in each number of the range, and finally return it.

 

Algorithm:

 

  • Initialise a variable “count” to store the total occurrences of ‘K’ in the range.
  • Start traversing through the range from [A, B], and check for each digit of the number:
    • If the digit is ‘K’:
      • Increment “count”
    • Else:
      • Continue
  • Return “count”
Time Complexity

O((B - A) * log(B)), where A and B are the lower and upper limits of the range.

 

In this approach, we are traversing through the complete range and for every number, we are traversing through all of its digits. So, the overall time complexity of this approach becomes O((B - A) * log(B)).

Space Complexity

O(1).

 

Since we are not using any extra space, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Digit Count In Range
Full screen
Console