Digit Count In Range

Posted: 12 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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”
Try Problem