Last Updated: 10 Sep, 2021

Find The Number

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

This approach will convert all the numbers into base 6 as base 6 will only have digits from 0-5. Therefore the N’th number in base 6, when written in base 10, will be N, the number with the given digits. We will have to decrease the number by one as 0 is the 1st number.

To convert any decimal number into any base, divide the number by base and add number / 10 converted to base multiplied by 10 to the remainder.

We will create a function base decimalToBase(number, base) to convert the number into the given base.

Algorithm:

In the function decimalToBase(number, base)
- If the number is equal to 0
  - Return 0
- Otherwise return decimalToBase(number / base) * 10 + number % base

Set baseSixNum as decimalToBase(N -1, 6)
Return baseSixNum

Solve now