Last Updated: 20 Apr, 2022
Count Numbers With Equal First and Last Digit
Moderate
Asked in companies
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’.
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
Approaches
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:
- Let ‘l’ to ‘r’ is the input range.
- Call the main function equalDigit( ‘l’ , ’r’ )
- Call the helper function ‘equalTillN’ for 'r' and 'l-1' separately.
- 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'.
- 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)’