Count Special Numbers

PROBLEM STATEMENT

A positive integer is called a Special Number if all the digits in its decimal representation lie between 1 to 5 (both inclusive). For example : 245, 312, etc. are some special numbers, whereas 340, 17, 0, etc. are some non-special numbers.

Given an integer 'N' . Your task is to find how many special numbers lie between 1 to N.

Input Format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first and only line of each test case contains the integer 'N'.

Output Format :

For each test case, print an integer denoting the total count of special numbers between 1 to N.

Print the output of each test case in a new line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10^4
1 <= N <= 10^9

Time Limit: 1 sec

Approach 1

The idea is to iterate through all the numbers that are smaller than or equal to N one by one and find the total count of special numbers. To check whether a particular number is a special number, we can check the number digit by digit to determine whether all the digits lie between 1 to 5. If yes, then the number is a special number. Otherwise, the number is not a special number.

Steps:

Define a variable specialNumbersFound to store the total count of special numbers. Initialize it as 0.
Iterate from i = 1 to N
- If i is a special number, then increment specialNumbersFound by 1.
  - To check whether a number is a special number, we will write a boolean function that takes an integer K as an argument and returns True if K is a special number, otherwise, it returns False.
  - Working of the checkSpecialNumber function
  - While K is greater than 0
    - Define rem as K % 10 to store the current rightmost digit of K.
    - If rem does not lie between 1 to 5, then we will return False.
    - Set K as K / 10.
  - If we have not returned False till now, then we will return True as all the digits we traversed were between 1 to 5. This means that K is a special number.
Return the specialNumbersFound variable.

Try Problem

Approach 2

The total number of d - digit numbers that are special is 5^d

For a d - digit number, each digit can have 5 possible values, i.e., 1, 2, 3, 4, and 5. The choice for any digit is independent of all the other digits. Therefore, by the rule of Product, we can infer that the total number of d - digit special numbers is 5^d.

Let N = N1 N2 … N(d-1) N(d) be a d - digit number.

We can easily count and add all the 1 digit, 2 digit … , d - 1 digit special numbers using the above formula. The sum obtained will be sum(5^i) for i = 1 to d - 1, which we can calculate naively or use the fact that the above sequence forms a Geometric Progression to obtain the result as (5*(5^(d-1)-1))/4. Let the obtained result be res.

Now it remains only to count the d - digit special numbers that are smaller than N, for which we will be using Digit - DP.

Steps:

Let each digit of N is stored in an array called digits
Initialize specialNumbersFound as 0.
Iterate through i = 0 to d - 1
- If i is equal to d - 1, then we will add the minimum value among 5 and digits[d-1] to specialNumbersFound, and end the loop. This serves as the base case.
- If digits[i] is 0, then we will end the loop, as the current digit is 0, and now no special number exists, which has not been calculated till now.
- Otherwise, if digits[i] is greater than 5, then we will add 5^(d-i) to specialNumbersFound, and end the loop. We are ending our process here because the current digit is greater than 5, and we have already added the count of special numbers having i'th digit less than or equal to 5. Hence, we need not go forward.
- Otherwise add (digits[i]-1)*(5^(d-i-1)) to specialNumbersFound variable, and move forward. In this case, we are not breaking because we have only found the special numbers whose i'th digit is smaller than digits[i], but we have not found the count of special numbers whose i'th digit is equal to digits[i].