Count Numbers With Equal First and Last Digit

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
SprinklrPhilips

Problem statement

Ninja has given a range represented by two positive integers ‘L’ and ‘R’. Find the count of numbers in the range where the first digit is equal to the last digit of the number.

Ninja called you for help as you are his only friend. Help him to solve the problem.

Example : 
Input: 'L' = 9 , ‘R’ = 12

Output: "2"

As ‘9’ and ‘11’ are the only numbers that have their first digit equal to the last digit. So the answer is ‘2’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

Each test case contains two space-separated integers ‘L’ and ‘R’.
Output format : 
For each test case, print the number of integers in [L, R] such that their first digit is equal to the last digit in those integers.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 1000
1 <= ‘L’ <= ‘R’ <= 10^18
Time Limit: 1 sec
Sample Input 1 :
2
8 12
19 35
Sample Output 1 :
3
2
Explanation Of Sample Input 1 :
In test case ‘1’. There are ‘3’ numbers satisfying the requirement that are ‘8’, ‘9’ and ‘11’. 
In test case ‘2’. There are ‘2’ numbers satisfying the requirement that are ‘22’ and ‘33’.
Sample Input 2 :
2
1 20
1 100
Sample Output 2 :
10
18
Hint

How many times in the least significant digit will match the most significant digit in 10 consecutive numbers? 

Approaches (1)
Constructive Approach

We will calculate answers for [1, L-1] and from [1,R] and will subtract answer( [1,R] )-answer( [1,L-1] ) to get final answer.

Let's see how we will calculate answers from 1 to ‘N’.

For ‘N’ <= 9: All numbers are having last digit equal to the first digit.

For ‘N’ >= 10: We know that for 10 consecutive digits the least significant digit changes ‘10’ times (0 to 9) and it will definitely match ‘1’ time with the most significant digit. And for the last ‘10’ numbers the first digit will match the last digit only if last_digit>=first_digit in the number ‘N’.

So if we have to find the answer from ‘1’ to ‘N’ then the answer will be simply = N/10 + (8 + (last digit >= first digit)).

 

The steps are as follows:  

  1. Let ‘l’ to ‘r’ is the input range.
  2. Call the main function equalDigit( ‘l’ , ’r’ )
  3. Call the helper function ‘equalTillN’ for 'r' and 'l-1' separately.
  4. Helper function which takes one argument 'n' and gave us how many numbers have the first digit equal to the last digit from 1 to 'n'.
  5. Inside the helper function ‘equalTillN’:
    • If n is less than '9' means all numbers have the first digit equal to the last digit.
    • Find the last digit in ‘n’.
    • Find the first digit in ‘n’.
    • Return answer according to the equation ‘int(n /10 ) + ( 8 + int( lastDigit >= firstDigit ) )’

Return ‘equalTillN(r)-equaltillN(l-1)’

Time Complexity

O( log10( max(‘L’, ‘R’ ) ) ), Where ‘L’ and ‘R’ are the input range.

 

As we are finding the most significant digit in both numbers.

Hence, the time complexity will be O(log10(max(‘L’, ‘R’))).

Space Complexity

O(1).

 

As we are maintaining a constant variable to store the answer.

Hence, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Count Numbers With Equal First and Last Digit
Full screen
Console