Last Updated: 19 Apr, 2021
Remove 9
Easy
Asked in companies
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.
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
Approaches
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:
- 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.
- Initialize ‘COUNTER’ as 0.
- 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 any digit is ‘9’:
- 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.
As every number changes to base 9 after the transformation of sequence of natural numbers, at every multiple of power of 10, we have some numbers containing 9, which we are removing. Hence due to 9 base, we need to iterate and divide the number with 9 till it reaches zero and multiply the multiply counter by 10 as 10 times more number will be removed as each multiply counter increases by 10 times.
[Note: Multiply counter is the power of 10, which increases itself by 10 times after each iteration. Because there are 10 times more integers that will contain the digit ‘9’ compared to the previous iteration and they need to be removed.]
Algorithm:
- Declare two variables ‘MUL_COUNTER’ and ‘ANS’ where ‘MUL_COUNTER’ denotes the current power value of 10 after each iteration and the variable ‘ANS’ denotes the answer that will be gradually storing our final answer as the ‘N’th digit in the new sequence.
- Initialize the ‘MUL_COUNTER’ as 1 and ‘ANS’ as 0.
- Run a loop while ‘N’ is greater than 0:
- Calculate remainder by dividing ‘N’ with 9 and store in ‘REM’.
- Increase ‘ANS’ by adding (‘REM’ * ‘MUL_COUNTER’) to the existing ‘ANS’.
- Divide ‘N’ by 9.
- Increase ‘MUL_COUNTER’ by ten times.
- Finally, return ‘ANS’.