Find The Number

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
19 upvotes
Asked in companies
AdobeEPAM Systems

Problem statement

You are given a number ‘N’. Your task is to find the N-th number that contains only the digits 0 1, 2, 3, 4, and 5.

Note: 
The number need not contain all the digits.
For example 
Consider ‘N’ = 4, the numbers containing only the given digits are [0, 1, 2, 3]. The 4th number is 3. Hence the answer is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the given integer.
Output Format: 
For each test case, print a single integer representing the N-th number containing only the given digits.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N <= 10^9

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
4
7
Sample Output 1:
3
10
Explanation:
For the first test case N = 4, the numbers containing only the given digits are [0, 1, 2, 3]. The 4th number is 3. Hence the answer is 4.

For the second test case, N = 7, the numbers containing only the given digits are [0, 1, 2, 3, 4, 5, 10]. The 7th number is 10. Hence the answer is 10.
Sample Input 2:
2
10
8
Sample Output 2:
13
11
Hint

 Build the numbers one by one.

Approaches (2)
Brute Force

In this approach, we will store the first 6 digits in an array. Then we can see the next numbers are [10, 11, 12, 13, 14, 15] and then [20, 21, 22, 23, 25, 25]. We can get the pattern by calculating the next 6 numbers like 10 + i, and then the next 6 as  20 + i, and so on. Each time we add 6 numbers, so we have to do this step N / 6 times. 

Therefore we are multiplying by the power of 10 and add numbers from 0 to 6.

 

Algorithm:

  • Initialise an empty array numbers
  • Iterate i from 0 to 5
    • Insert i into numbers
  • Iterate i from 0 to n/ 6
    • Iterate j from 0 to 5
      • If numbers[i]*10 is not equal to 0
        • Insert numbers[i]*10 + numbers[j] into numbers
  • Return the last elements in numbers
Time Complexity

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

 

We are inserting N numbers in the array, which will take O(N) time. Hence the final time complexity is O(N).

Space Complexity

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

 

We are maintaining an array to store the integers that will cost O(N). Hence the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Find The Number
Full screen
Console