Count Special Numbers

Posted: 26 Feb, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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:

  1. Define a variable specialNumbersFound to store the total count of special numbers. Initialize it as 0.
  2. Iterate from i = 1 to
    • 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.
  3. Return the specialNumbersFound variable.
Try Problem