Remove 9

Easy
0/40
Average time to solve is 15m
5 upvotes
Asked in companies
DunzoCitrixCrowe

Problem statement

A committee of mathematicians decided to remove every natural number which contains digit 9 such as 9, 19, 29, ... . Hence the new sequence of natural numbers will be: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ….

Given the natural number ‘N’, can you find the ‘N’th number in the new sequence formed after removing every integer that contains 9?

Note:

The sequence of natural numbers are integers that start from 1.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then each test case follows.

The first and the only line of each test case contains an Integer ‘N’ denoting the Nth natural number to find in the new sequence of natural numbers.

Output Format:

For each test case, return the Nth natural number starting from 1 in the new sequence of natural numbers defined by a committee of mathematicians.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 10^5

Time Limit: 1 sec
Sample Input 1:
 2
 19
 50
Sample Output 1:
21
55

Explanation for Sample 1:

For the first test case: 
The 19th number in a normal sequence of natural numbers is 19. But till 19, there are 2 numbers which contain 9 which are 9 and 19 respectively.
And hence excluding these two numbers from the sequence, we will have 19+2 = 21 as our 19t’h integer in the new sequence.

For the second test case: 
The 50th number in a normal sequence of natural numbers is 50. But till 50, there are 5 numbers which contain 9 which are 9,19,29,39,49 respectively.
And hence excluding these five numbers from the sequence, we will have 50+5 = 55 as our 50t’h integer in the new sequence.
Sample Input 2:
 2
 11
 81
Sample Output 2:
12
100

Explanation for Sample 2:

For the first test case: 
The 11th number in a normal sequence of natural numbers is 11. But till 11, there is 1 number which contains 9 which is 9 itself.
And hence excluding these ‘9’ from the sequence, we will have 11+1 = 12 as our 11t’h integer in the new sequence.

For the second test case: 
The 81st number in a normal sequence of natural numbers is 81. But till 81, there are 8 numbers which contain 9 which are 9,19,29,39,49,59,69,79 respectively.
And hence excluding these eight numbers from the sequence, we will have 81+8 = 89. But numbers 89, 90, ..., 99 (total 11 integers)  also contain digit 9 and hence our 81st integer will be 89+11 = 100 which does not contain the digit 9.
Hint

Can you think of by iterating every integer from 1?

Approaches (2)
Brute Force

We need to start iterating from 1 and check for every integer. If an integer contains 9, then ignore that integer and move forward till we get our ‘N’th integer that doesn’t contain the digit 9.

 

Algorithm:

 

  1. Declare two variables. Integer variable ‘COUNTER’ and a boolean variable ‘FLAG’. Where ‘COUNTER’ denotes the count of numbers which does not contain the digit 9 and variable ‘FLAG’ for every integer in interaction which will be true if the integer contains the digit 9.
  2. Initialize ‘COUNTER’ as 0.
  3. Run the for loop with variable ‘i’ starting from 1 and no breaking condition:
    • Assign the value ‘i’ to the variable ‘NUM’.
    • Initialize ‘FLAG’ as false.
    • Run a loop while ‘NUM’ is greater than 0 which will check every digit of the integer ‘i’.
      • If any digit is ‘9’:
        • ‘FLAG’ as true
        • break
      • Else:
        • divide ‘NUM’ by 10.
    • If variable ‘FLAG’ is true, go for the next integer ‘i’ in the loop.
    • But if ‘FLAG’ is false:
      • increase the ‘COUNTER’ by 1.
    • Finally, check if the ‘COUNTER’ gains the value equal to ‘N’:
      • return the current integer ‘i’ which will be the ‘N’th integer in the new sequence formed.
Time Complexity

O(K * log10(K)), where ‘K’ denotes the ‘N’th natural number we need to find in the new sequence of natural numbers.

 

Because we are iterating till the integer ‘K’ to find our ‘N’th natural number in the new sequence and for every integer, till ‘K’ we are checking every digit in the integer which takes max O(log10(K)) time. And thus the total time complexity will be of the order O(K * log10(K)).

Space Complexity

O(1).

 

Because we are not using any extra space for calculating our answer.

Code Solution
(100% EXP penalty)
Remove 9
Full screen
Console