Special Numbers

Moderate
0/80
Average time to solve is 25m
0 upvote
Asked in company
Morgan Stanley

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
6
Sample Output 1:
1
5
Explanation for Sample Input 1:
For the first test case, the first two special numbers are 0 and 1. Hence the second special number is 1.
For the second test case, the first 6special numbers are 0, 1, 2, 3, 4, and 5. Hence the sixth special number is 5.
Sample Input 2:
2
10
18
Sample Output 2:
13
25
Hint

Can you observe some pattern here?

Approaches (2)
Brute-force

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

O(N), where N is the given number.

 

Here we are just iterating from 0 to N / 6. So, the overall time complexity is O(N).

Space Complexity

O(N), where N is the given number.

 

We are using the ans vector, which will have the length ‘N’. Hence, the overall space complexity is O(N).

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