Special Numbers

Posted: 2 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

A special number is defined as a number in which each digit of the number is between 0 to 5 (both inclusive) i.e. each digit belongs to the set S = {0, 1, 2, 3, 4, 5}.

Given a number N, your task is to find the Nth special number.

Input Format
The first line of input contains an integer T representing the number of test cases.

The first line of each test case contains one integer N denoting the number.
Output Format:
For each test case, on a separate line, output one integer - Nth special number.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 1000
1 <= N <= 10^6

Where ‘T’ is the number of test cases, ‘N’  the given number.

Time limit: 1 sec
Approach 1

Approach : 

 

The first six special numbers are 0, 1, 2, 3, 4 and 5. The next six special numbers are 10, 11, 12, 13, 14 and 15. The next six special numbers are 20, 21, 22, 23, 24, 25, and so on.

 

A pattern can be observed here for the chains of six- 

Let’s say we have an ans array initially filled with numbers from 0 to 5, i.e the 1st six special numbers. The next chain of numbers in the series would be nothing but 10 * 1 + 0 = 10, 10 * 1 + 1, ……., 10 * 1 + 5.  The next chain would be 10 * 2 + 0, 10 * 2 + 1, ………., 10 * 2 + 5.

Similarly, the i-th chain would be 10 * ans[i] + 0, 10 * ans[i] + 1, ………, 10 * ans[i] + 5.

 

The algorithm is as follows - 

  • Declare an ‘ans’ array and push 0 to 5 in it.
  • Iterate from i = 0 to N / 6.
    • Iterate from j = 0 to 5:
      • Append ans[i] * 10 + ans[j] to ans, if ans[i] * 10 != 0.
      • If ans[i] * 10 is 0 then we will be left with ans[j] and we have already inserted ans[j] in the and, hence there is no need to insert it again.
  • Finally, return ans[n - 1].
Try Problem