# Special Numbers

Posted: 2 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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].