Count Special Numbers

Hard
0/120
Average time to solve is 30m
profile
Contributed by
10 upvotes
Asked in company
Morgan Stanley

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
7
13

Sample Output 1 :

5 
8
Explanation for Sample Input 1 :
For the first test case : 
All the special numbers that are smaller than 7 are [ 1, 2, 3, 4, 5 ]. Hence, the answer is 5 in this case.

For the second test case : 
All the special numbers that are smaller than 13 are [ 1, 2, 3, 4, 5, 11, 12, 13 ]. Hence, the answer is 8 in this case.

Sample Input 2 :

2
2
20

Sample Output 2 :

2
10
Hint

Iterate through all numbers from 1 to N, and for every number, check whether it is a special number.

Approaches (2)
Brute Force Approach

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 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.
  3. Return the specialNumbersFound variable.
Time Complexity

O(N*log10(N)), where N is the input number.

 

As we are iterating through each value from 1 to N, and it takes O(log10(N)) time to check whether a particular number is a special number. Hence, the overall Time Complexity is O(N*log10(N)).

Space Complexity

O(1).

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Count Special Numbers
Full screen
Console