The $n$-th number that contains the digit $k$ or is divisible by $k$ ($2 \le k\le 9$)

Question

I need to find the $n$-th number that contains the digit $k$ or is divisible by $k$, where $2 \leqslant k \leqslant 9$.

Example: If $n = 15$ and $k = 3$, then the answer is

$$ 33\quad (3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 32, 33)$$

I started following the sequence but couldn't formulate it:

• for multiples of $3 \to 3+3+3+4+3+3+4+3+3+4$

• for containing digit $3 \to 1+1+1+10+1+1+1+1+1+1$

I have to answer in better than $\mathcal O(n)$ or in $\mathcal O(1)$ if possible. Please don't suggest methods that checks every number in a for loop. Thanks.

Edit: I have searched everywhere but couldn't find it answered anywhere. So, it's not a duplicate.

Answer 1

Say a number is good if it is a multiple of $k$ or contains the digit $k$ (or both). The key idea is to find a fast way to compute $f(m)$, the number of good numbers $< m$. With such a function $f$ at hand, you can find the desired result, namely one less that the smallest $m$ with $f(m)=n$ by binary search (starting with $n$ as lower bound and $nk$ as upper bound). This requires $\log(nk)$ calls to $f$, so we better find a fast implementation of $f$.

We make use of a helper function: Assume $a$ is a multiple of $10^q$ and does not contain digit $k$. Assume $a\equiv r\pmod k$. Then $f(a+10^q)-f(a)$ depends only on $q$ and $r$, so let's call this value $g(q,r)$. We can precompute and memoize $g$ for all combinatons of $0\le q<\lceil\log_{10}n\rceil$ and $0\le r<k$ as follows:

We have $$g(0,r)=\begin{cases}1&\text{r=0}\\0&\text{otherwise}\end{cases}$$ and $$g(q+1,r)=10^q+\sum_{j=0\atop j\ne k}^9 g\bigl (q,r+(10^qj\bmod k)\bigr ).$$ Using this, we can compute $f(n)$ by adding at most digit-sum of $n$ such values of $g$ (where you have to be careful in the beginning if $n$ itself contains a digit $k$)

The whole computation costs $O(\log(n)^2)$ time and $O(\log(n))$ space.

---

I think the following might be close to working (provided you have getG):

typedef unsigned long long  number;
define numberFormat  "%llu"

define MAXDIGITS (3 * sizeof(number))   // very generous  
define MAXNUMBER ((number)-1)  // assumes number is unsigned

number goodUpToIncluding(number n, int k) {
   // assume n>0 and 1<k<10
   number result = 0;
   int q = 0;
   number q10 = 1;  // always q10 = 10^q
   while (n/q10 >= 10) {
      q++;
      q10 *= 10;
   }
   while (q>0) {
      if ((n/q10) % 10 == k) {
          number step = (n % q10)+1;
          result += step;
          n -= step;
      }
      q--;
      q10 /= 10;
   }
   // Now n does not contain digit k ...
   if (n % k == 0) result++; // ... hence check only for divisibilty
   // From now on, we count *excluding* n
   while (n>0) {
      while ( (n/10 >= q10 && n % (10*q10) == 0) {
         q++;
         q10 *= 10;
      }
      // n ends in exactly q zeroes (is divisible by q10)
      n -= q10;
      if ((n/q10) % 10 == k) { // a full block of good numbers
         n -= q10;
         result += q10;
      }
      result += getG(q,n % k);
   }
   return result-1; // -1 to compensate for counting 0 as good
}

number getNthGoodNumber(number n, k) {
   number low = 0, high = MAXNUMBER;
   while (high - low > 1) {
      number middle = (high+low)/2;
      number goodMiddle = goodUpToIncluding(middle,k);
      if (goodMiddle < n) 
         low = middle;
      else 
         high = middle;
   }
   return high;
}

Answer 2

This is a dynamic programming problem. If we have a function that counts up how many numbers over $1 \leq i \leq N$ (for some boundary limit $N$) are divisible by $k$ or contain a digit $k$, then we can use a binary search to find when it returns $n$ (the target number).

So now we need a fast way to count up the relevant numbers over the range $1 \leq i \leq N$ for some $N$, which we can initialize to $9n$ (as this will be a hard upper bound).

Iterating from the leftmost digit position of $N$ towards the right, we can parameterize each state of the recursion by:

1. The remaining digits of $N$
2. The value of $k$
3. The residue of the number traced so far through the DP, modulo $k$
4. A flag stating whether or not we've been tracing along the exact digits of $N$ so far
5. A flag stating whether or not we've already encountered digit $k$ in our traced number so far

Then by the time we are at the end of the DP (i.e. when there are no more digit positions of $N$ to iterate though), we return $1$ if the residue is equal to $0$ (meaning the number we traced was divisible by $k$) or if the seen-$k$ flag is true.

The $N$-tracing flag prevents us from tracing numbers that exceed $N$. For example, if $N=47262$, then on the far left digit position, we can recurse with digits $0$ through $4$ and nothing greater. But if we decide to recurse with anything less than $4$, then we are no longer bound by this restriction going forward and we can start picking digits in the full $0-9$ range. But if we do choose $4$, then we must be bound from above by $7$ when we move to the next digit position.

This runs in $O(\log(n)^2)$ time and $O(\log(n))$ space.