Find nth number that contains the digit k or divisible by k in C++

Given two positive integers n and k, and we have to find the nth number that contains the digit k or divisible by k. The k will be in range [2 to 9]. So if n and k are 15 and 3 respectively, then output is 33. As the numbers [3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 33] These are those numbers where each element contains the digit k = 3 or divisibility by k and in this nth number is 33. So output is 33.

Check each number that contains k and multiple of k, and count till we get nth element.

Example

 Live Demo

#include<iostream> using namespace std; bool hasDigit(int n, int k) {    while (n > 0) {       int rem = n % 10;       if (rem == k)       return true;       n = n / 10;    }    return false; } int countNumbers(int n, int k) {    for (int i = k + 1, count = 1; count < n; i++) {       if (hasDigit(i, k) || (i % k == 0))          count++;       if (count == n)          return i;    }    return -1; } int main() {    int n = 10, k = 2;    cout << "Last number is " << countNumbers(n, k) << " before that the number contains " << k << " and multiple of " << k; }

Output

Last number is 20 before that the number contains 2 and multiple of 2