Digit Count In Range
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

Question

Digit Count In Range

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

Accepted Answer

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”

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: OtherExplanation:

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)).

Accepted Answer

Recursion and Basic Mathematics

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.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(logn)Explanation:

O(log(B), where B is the upper limit of the given range.

Since we are traversing through the digits of the given integer and the number of digits in A and B is equal to log base 10 of A and B, overall time complexity is O(log(B)).

Java (SE 1.8)

/*



	Time complexity: O(log(B)) 

	Space complexity: O(1)



    where B is the upper limit of the given range

	

*/



public class Solution 

{

	private static long countDigit(long N, int K) 

    {

		// variable to store count

		long count = 0;



		// start traversing from 1 to N

		for (long i = 1; i <= N; i *= 10) 

        {

			// variables to store divisor, quotient and remainder

			long divi = i * 10;

			long quot = (N / divi);

			long rema = N % divi;



			// condition 1

			if (quot > 0) 

            {

				count = count + (quot * i);

			}



			// Condition 2

			if (K == 0) 

            {

				count = count - i;

			}



			// Condition 3

			if (rema >= K * i) 

            {

				count = count + (Math.min(rema - K * i + 1, i));

			}

		}



		// return count

		return count;

	}



	public static long digitCount(int K, long A, long B)

    {

		// Recursive function to calculate count of 'K' in [0, N]

		return countDigit(B, K) - countDigit((A - 1), K);

	}

}

Python (3.5)

'''



	Time complexity: O(log(B)) 

	Space complexity: O(1)



    where B is the upper limit of the given range

	

'''



def countDigit(N, K):



    # variable to store count

    count = 0

	

    # start traversing from 1 to N

    i = 1

    

    while(i <= N):

        

        # variables to store divisor, quotient and remainder

        divi = i * 10

        quot = N // divi

        rema = N % divi



        # condition 1

        if (quot > 0):

        	count = count + (quot * i)

        

        # Condition 2

        if (K == 0):

          	count = count - i

        

        # Condition 3

        if (rema >= K * i):

          	count = count + (min(rema - K * i + 1, i))

        

        i *= 10

    

    # return count

    return count





def digitCount(K, A, B):



    # Recursive function to calculate count of 'K' in [0, N]

    return countDigit(B, K) - countDigit((A - 1), K)

C++ (g++ 5.4)

/*



	Time complexity: O(log(B)) 

	Space complexity: O(1)



    where B is the upper limit of the given range	



*/



#include



long long int countDigit(long long int N, int K)

{

    // variable to store count

    long long int count = 0;

	

    // start traversing from 1 to N

    for (long long int i = 1; i <= N; i *= 10) 

    {       

        // variables to store divisor, quotient and remainder

      	long long int divi = i * 10;

      	long long int quot = N / divi;

      	long long int rema = N % divi;



        // condition 1

      	if (quot > 0)

      	{

        	count = count + (quot * i);

      	}

        

        // Condition 2

      	if (K == 0)

      	{

          	count = count - i;

      	}

        

        // Condition 3

      	if (rema >= K * i)

      	{  

          	count = count + (min(rema - K * i + 1, i));

    	}

    }

    

    // return count

    return count;

}



long long int digitCount(int K, long long int A, long long int B)

{

    // Recursive function to calculate count of 'K' in [0, N]

    return countDigit(B, K) - countDigit((A - 1), K);

}

Accepted Answer

/ *
java solution:
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
        int base=10;
        char init=Character.forDigit(k,base);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=0;
        for(int i=a;i<=b;i++){
            String str=""+i;
            char[] arr=str.toCharArray();
            for(char chh:arr){
                if(chh==init){
                    c+=1;
                }
            }
        }
        System.out.println(c);
    }
*/

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:

For example :

Input Format:

Output Format:

Note:

Constraints:

Top Paxcom India Software Developer interview questions & answers

Popular interview questions of Software Developer