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:
Input: N = 12, K = 2
Output: 14
Explanation: 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 infinityInput: N = 10, K = 1
Output: 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.
- Initialize count to 0 and i to 1
- While count is less than n:
- Check if i contains the digit k by calling the containsDigit function
- If i does not contain k:
- Increment count by 1
- If count is equal to n:
- Return i as the nth natural number that does not contain k.
- Otherwise, increment i by 1 and continue to the next iteration of the loop
- If we have iterated up to N without finding the nth natural number that does not contain k, return -1 (this is an error condition)
- containsDigit function:
- Initialize a variable called numCopy to the value of num
- While numCopy is greater than 0:
- Check if the last digit of numCopy is equal to k
- If it is, return true
- Otherwise, divide numCopy by 10 to remove the last digit.
- If we have checked all the digits in num and have not found k, return false.
C++
#include <iostream>using namespace std;bool containsDigit(int num, int digit){ while (num > 0) { if (num % 10 == digit) { return true; } num /= 10; } return false;}int findNthNumber(int n, int k){ int count = 0; int i = 1; while (count < n) { if (!containsDigit(i, k)) { count++; } if (count == n) { return i; } i++; } return -1;}int main(){ int n = 12; int k = 2; int nthNumber = findNthNumber(n, k); cout << "The " << n << "th natural number not containing " << k << " is: " << nthNumber << endl; return 0;} |
Java
// Java program for the above approachpublic class Main { public static boolean containsDigit(int num, int digit) { // Check if the given number contains the given digit while (num > 0) { if (num % 10 == digit) { return true; } num /= 10; // Integer division } return false; } // Find the nth natural number that does not contain the digit k public static int findNthNumber(int n, int k) { int count = 0; int i = 1; while (count < n) { if (!containsDigit(i, k)) { count++; } if (count == n) { return i; } i++; } return -1; } public static void main(String[] args) { int n = 12; int k = 2; int nthNumber = findNthNumber(n, k); System.out.println("The " + n + "th natural number not containing " + k + " is: " + nthNumber); }} |
Python3
# codedef contains_digit(num, digit): # Check if the given number contains the given digit while num > 0: if num % 10 == digit: return True num //= 10 # Integer division return Falsedef find_nth_number(n, k): # Find the nth natural number that does not contain the digit k count = 0 i = 1 while count < n: if not contains_digit(i, k): count += 1 if count == n: return i i += 1 return -1if __name__ == "__main__": n = 12 k = 2 nth_number = find_nth_number(n, k) print(f"The {n}th natural number not containing {k} is: {nth_number}") |
C#
using System;public class GFG{ public static bool ContainsDigit(int num, int digit) { // Check if the given number contains the given digit while (num > 0) { if (num % 10 == digit) { return true; } num /= 10; // Integer division } return false; } // Find the nth natural number that does not contain the digit k public static int FindNthNumber(int n, int k) { int count = 0; int i = 1; while (count < n) { if (!ContainsDigit(i, k)) { count++; } if (count == n) { return i; } i++; } return -1; } public static void Main(string[] args) { int n = 12; int k = 2; int nthNumber = FindNthNumber(n, k); Console.WriteLine("The " + n + "th natural number not containing " + k + " is: " + nthNumber); }}// This code is contributed by guptapratik |
Javascript
// Nikunj Sonigarafunction containsDigit(num, digit) { while (num > 0) { if (num % 10 === digit) { return true; } num = Math.floor(num / 10); } return false;}function findNthNumber(n, k) { let count = 0; let i = 1; while (count < n) { if (!containsDigit(i, k)) { count++; } if (count === n) { return i; } i++; } return -1;}function main() { let n = 12; let k = 2; let nthNumber = findNthNumber(n, k); console.log("The " + n + "th natural number not containing " + k + " is: " + nthNumber);}main(); |
Output
The 12th natural number not containing 2 is: 14
Time Complexity: O(N*d), where N is the input value and d is the number of digits in N.
Auxiliary Space: O(1)
Efficient Approach: The efficient approach to solve this is inspired by the Nth natural number after removing all numbers consisting of the digit 9.
The given problem can be solved by converting the value of K to base 9 forms 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 codeint main(){ long long N = 12, K = 2; long long base9 = convertToBase9(N); cout << getNthnumber(base9, K); return 0;} |
Java
// Java implementation for the above approachimport 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 approachdef 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 ansdef 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 codeif __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 approachusing 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 approachfunction 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 codelet N = 10, K = 1;let base9 = convertToBase9(N);document.write(getNthnumber(base9, K));// This code is contributed by gfgking.</script> |
Output
14
Time Complexity: O(log9N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!