# Finding the Nth term in a sequence formed by removing digit K from natural numbers

Given the integers **N, K **and an infinite sequence of natural numbers where all the numbers containing the digit **K **(1<=K<=9) are removed. The task is to return the **Nth** number of this sequence.

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 12, K = 2Output:14Explanation:The sequence generated for the above input would be like this: 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, up to infinity

Input:N = 10, K = 1Output:22

**Naive Approach: **The basic approach to solving the above problem would be to iterate up to N and keep excluding all numbers less than N containing the given digit K. Finally, print the Nth natural number obtained.

Time Complexity: O(N)

Auxiliary Space: O(1)

**Efficient Approach:** The efficient approach to solve this is inspired from Nth natural number after removing all numbers consisting of the digit 9.

Given problem can be solved by converting the value of **K** to base 9 form if it is more than 8. Below steps can be followed:

- Calculate the Nth natural number to base 9 format
- Increment 1 to every digit of the base 9 number which is greater than or equal to K
- The next number is the desired answer

Below is the code for the above approach:

## C++

`// C++ implementation for the above approach` `#include <iostream>` `using` `namespace` `std;` `long` `long` `convertToBase9(` `long` `long` `n)` `{` ` ` `long` `long` `ans = 0;` ` ` `// Denotes the digit place` ` ` `long` `long` `a = 1;` ` ` `// Method to convert any number` ` ` `// to binary equivalent` ` ` `while` `(n > 0) {` ` ` `ans += (a * (n % 9));` ` ` `a *= 10;` ` ` `n /= 9;` ` ` `}` ` ` `return` `ans;` `}` `long` `long` `getNthnumber(` `long` `long` `base9,` ` ` `long` `long` `K)` `{` ` ` `long` `long` `ans = 0;` ` ` `// denotes the current digits place` ` ` `long` `long` `a = 1;` ` ` `while` `(base9 > 0) {` ` ` `int` `cur = base9 % 10;` ` ` `// If current digit is >= K` ` ` `// increment its value by 1` ` ` `if` `(cur >= K) {` ` ` `ans += a * (cur + 1);` ` ` `}` ` ` `// Else add the digit as it is` ` ` `else` `{` ` ` `ans += a * cur;` ` ` `}` ` ` `base9 /= 10;` ` ` `// Move to the next digit` ` ` `a *= 10;` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `int` `main()` `{` ` ` `long` `long` `N = 10, K = 1;` ` ` `long` `long` `base9 = convertToBase9(N);` ` ` `cout << getNthnumber(base9, K);` ` ` `return` `0;` `}` |

## Java

`// Java implementation for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` ` ` `static` `long` `convertToBase9(` `long` `n)` ` ` `{` ` ` `long` `ans = ` `0` `;` ` ` `// Denotes the digit place` ` ` `long` `a = ` `1` `;` ` ` `// Method to convert any number` ` ` `// to binary equivalent` ` ` `while` `(n > ` `0` `) {` ` ` `ans += (a * (n % ` `9` `));` ` ` `a *= ` `10` `;` ` ` `n /= ` `9` `;` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `static` `long` `getNthnumber(` `long` `base9,` ` ` `long` `K)` ` ` `{` ` ` `long` `ans = ` `0` `;` ` ` `// denotes the current digits place` ` ` `long` `a = ` `1` `;` ` ` `while` `(base9 > ` `0` `) {` ` ` `int` `cur = (` `int` `)(base9 % ` `10` `);` ` ` `// If current digit is >= K` ` ` `// increment its value by 1` ` ` `if` `(cur >= K) {` ` ` `ans += a * (cur + ` `1` `);` ` ` `}` ` ` `// Else add the digit as it is` ` ` `else` `{` ` ` `ans += a * cur;` ` ` `}` ` ` `base9 /= ` `10` `;` ` ` `// Move to the next digit` ` ` `a *= ` `10` `;` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main (String[] args) {` ` ` `long` `N = ` `10` `, K = ` `1` `;` ` ` `long` `base9 = convertToBase9(N);` ` ` `System.out.println(getNthnumber(base9, K));` ` ` `}` `}` `// This code is contributed by Dharanendra L V.` |

## Python3

`# Python 3 implementation for the above approach` `def` `convertToBase9(n):` ` ` `ans ` `=` `0` ` ` ` ` `# Denotes the digit place` ` ` `a ` `=` `1` ` ` `# Method to convert any number` ` ` `# to binary equivalent` ` ` `while` `(n > ` `0` `):` ` ` `ans ` `+` `=` `(a ` `*` `(n ` `%` `9` `))` ` ` `a ` `*` `=` `10` ` ` `n ` `/` `/` `=` `9` ` ` `return` `ans` `def` `getNthnumber(base9, K):` ` ` `ans ` `=` `0` ` ` `# denotes the current digits place` ` ` `a ` `=` `1` ` ` `while` `(base9 > ` `0` `):` ` ` `cur ` `=` `base9 ` `%` `10` ` ` `# If current digit is >= K` ` ` `# increment its value by 1` ` ` `if` `(cur >` `=` `K):` ` ` `ans ` `+` `=` `a ` `*` `(cur ` `+` `1` `)` ` ` `# Else add the digit as it is` ` ` `else` `:` ` ` `ans ` `+` `=` `a ` `*` `cur` ` ` `base9 ` `/` `/` `=` `10` ` ` `# Move to the next digit` ` ` `a ` `*` `=` `10` ` ` `return` `ans` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `10` ` ` `K ` `=` `1` ` ` `base9 ` `=` `convertToBase9(N)` ` ` `print` `(getNthnumber(base9, K))` ` ` ` ` `# This code is contributed by SURENDRA_GANGWAR.` |

## C#

`// C# implementation for the above approach` `using` `System;` `class` `GFG {` ` ` ` ` `static` `long` `convertToBase9(` `long` `n)` ` ` `{` ` ` `long` `ans = 0;` ` ` `// Denotes the digit place` ` ` `long` `a = 1;` ` ` `// Method to convert any number` ` ` `// to binary equivalent` ` ` `while` `(n > 0) {` ` ` `ans += (a * (n % 9));` ` ` `a *= 10;` ` ` `n /= 9;` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `static` `long` `getNthnumber(` `long` `base9,` ` ` `long` `K)` ` ` `{` ` ` `long` `ans = 0;` ` ` `// denotes the current digits place` ` ` `long` `a = 1;` ` ` `while` `(base9 > 0) {` ` ` `int` `cur = (` `int` `)(base9 % 10);` ` ` `// If current digit is >= K` ` ` `// increment its value by 1` ` ` `if` `(cur >= K) {` ` ` `ans += a * (cur + 1);` ` ` `}` ` ` `// Else add the digit as it is` ` ` `else` `{` ` ` `ans += a * cur;` ` ` `}` ` ` `base9 /= 10;` ` ` `// Move to the next digit` ` ` `a *= 10;` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main (String[] args) {` ` ` `long` `N = 10, K = 1;` ` ` `long` `base9 = convertToBase9(N);` ` ` `Console.Write(getNthnumber(base9, K));` ` ` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Javascript

`<script>` `// Javascript implementation for the above approach` `function` `convertToBase9(n)` `{` ` ` `let ans = 0;` ` ` `// Denotes the digit place` ` ` `let a = 1;` ` ` `// Method to convert any number` ` ` `// to binary equivalent` ` ` `while` `(n > 0) {` ` ` `ans += a * (n % 9);` ` ` `a *= 10;` ` ` `n = Math.floor(n / 9);` ` ` `}` ` ` `return` `ans;` `}` `function` `getNthnumber(base9, K) {` ` ` `let ans = 0;` ` ` `// denotes the current digits place` ` ` `let a = 1;` ` ` `while` `(base9 > 0) {` ` ` `let cur = base9 % 10;` ` ` `// If current digit is >= K` ` ` `// increment its value by 1` ` ` `if` `(cur >= K) {` ` ` `ans += a * (cur + 1);` ` ` `}` ` ` `// Else add the digit as it is` ` ` `else` `{` ` ` `ans += a * cur;` ` ` `}` ` ` `base9 = Math.floor(base9 / 10);` ` ` `// Move to the next digit` ` ` `a *= 10;` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `let N = 10,` ` ` `K = 1;` `let base9 = convertToBase9(N);` `document.write(getNthnumber(base9, K));` `// This code is contributed by gfgking.` `</script>` |

**Output:**

22

**Time Complexity:** O(log_{9}N)**Auxiliary Space: **O(1)