Last Updated: 12 Mar, 2021

Digit Count In Range

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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”

Solve now

02 Approach

In this approach, we will create a recursive function, then calculate the number of occurrences of ‘K’, in the range [1, A - 1] and [1, B], then subtract them to get the occurrences of ‘K’ in the range [A, B].

Also for calculating the occurrences, we will find a pattern, so that we don’t need to traverse through every number.

Pattern Generation:

We will start by counting occurrences of let’s say 1 in ones place, then in tens place and further in hundreds places.

We found that the digit '1' at ones place repeats in group of 1 after an interval of 10.

Similarly, '1' at tens place repeats in groups of 10 after intervals of 100.

This can simply be formulated as (N / (interval * 10)) * interval, where N is the given number.

Also note that, if the digit at tens place is ‘1’, then the number of terms with ’1’s is increased by x+1, if the number is say "ab1x". As if digits at tens place is greater than 1, then all the 10 occurrences of numbers with ‘1' at tens place have taken place, hence, we add 10. This is formulated as min(max((n mod (i * 10)) − i + 1, 0), i).

Let's take an example, N = 1234, means it is either the upper limit or the lower limit of the range and K = 1.
No of ’1’ in ones place = 1234 / 10 (corresponding to 1, 11, 21,... 1221) + min(4, 1) (corresponding to 1231) = 124
No of ’1’ in tens place = (1234 / 100) ∗ 10(corresponding to 10, 11, 12,..., 110, 111,... 1919) +
min(21, 10) (corresponding to 1210, 1211,...1 219) = 130
No of ’1’ in hundreds place = (1234 / 1000) ∗ 100(corresponding to 100,101,12,...,199) + min(135, 100) (corresponding to 1100, 1101… 1199) = 200
No of ’1’ in thousands place = (1234 / 10000) ∗ 10000 + min(235, 1000) (corresponding to 1000, 1001,... 1234) = 235
Therefore, Total = 124 + 130 + 200 + 235 = 689.

Algorithm:

Create a recursive function that calculates the occurrence of ‘K’ in range [0, N].
Recursively call for N = A and N = B
Iterate over i from 1 to n incrementing by 10 each time:
- Add (n / (i ∗ 10)) ∗ i to “count” representing the repetition of groups of i sizes after each (i * 10) interval.
- Add min(max((n mod (i * 10)) − i + 1, 0), i) to “count” representing the additional digits dependent on the digit in ith place as described in intuition.
Subtract results from the two recursive solutions and return it.

Solve now