Last Updated: 2 Mar, 2021

Special Numbers

Moderate

Asked in company

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

Approach :

If we have a number with a base of 10, then each digit of the number will be from 0 to 9. Similarly, if each digit of a number is from 0 to X, then the number can be represented in base X+1. Since a special number has digits from 0 to 5, and the special number series starts from 0, we observe that specialNumber(N) is equal to the base 6 representation of N - 1.

Hence to find the Nth special number it is sufficient to find the base 6 representation of N - 1. This can be done with the help of the following recursive formula.

specialNumber(N) = (N) % 6) + (10 * specialNumber((N) / 6)).

For example, the base 6 representation of 15 is 23, by repeatedly dividing N by 6 and storing the remainders.

15 base 6 = (15 % 6) + 10 * Base 6 representation of (15 / 6).

= 3 + (10 * Base 6 representation of (2))

= 3 + (10 * 2)

= 23

Here, digit 2 corresponds to 10^1-th power, and digit 3 corresponds to 10^0-th power.

The algorithm is as follows -

First, subtract the number N by 1.
Then, convert the number to base 6.
- Implement a recursive function specialNumber(N).
- If N < 6, then our ‘ans’ is simply N, so return it. This will serve as the base case in our recursive function.
- Else, return (N % 6) + (10 * specialNumber(N / 6)).
- Covert the number to base 6 by calculating the remainder and adding it again and again to get the result.

Solve now