Algorithm (N-ary Tree Traversal)

1. Note that a number $x$ start with $a\leq x$ form a $10$-nary tree with root $a$, which we denote as $\mathcal{T}(a)$. In other words, each number that is less that $n$ and start with $a$ corresponds to unique chain in tree $\mathcal{T}(a).$
2. Let $f(i,\text{rank})$ denote the $\text{rank}-$th lexicographical smallest number when counting from $i\in\{1,....,n\}.$
3. Then we have $$f(i,\text{rank})=\begin{cases} i & \text{if }\text{rank}=1\\\\ f(10i,\text{rank}-1) & \text{else if }\mathrm{size}(\mathcal{T}(i)\geq\text{rank}\\\\ f(i+1,\text{rank}-\text{size}(\mathcal{T}(i)) & \text{else if }\mathrm{size}(\mathcal{T}(i)<\text{rank} \end{cases}.$$ The final solution is $f(1,k).$
4. The evalutation of $\mathrm{size}(T(i))$ will be too slow if done naively. Hence, we use an alternative implementation $\mathrm{\widehat{size}}(\mathcal{T}(i),l),$ which means the number of nodes in $\mathcal{T}(i)$ when counting from level $l$. It is the following recursive definition: $$\widehat{\mathrm{size}}(\mathcal{T}(i),l)=\begin{cases} 1 & \text{if }l=0\\\\ 10^{l}+\widehat{\mathrm{size}}(\mathcal{T}(10i,l+1)) & \text{else if }\mathrm{span}(\mathcal{T}(i),l)\subset(-\infty,n]\\\\ 0 & \text{else if }(-\infty,n]\cap\mathrm{span}(\mathcal{T}(i),l)=\emptyset\\\\ n-\min(\mathrm{span}(\text{level}(\mathcal{T}(i),l))) & \text{else if }(-\infty,n]\cap\mathrm{span}(\mathcal{T}(i),l)\neq\emptyset \end{cases},$$ where $\mathrm{span}(\mathcal{T}(i),l)$ computes the numerics range of $\mathcal{T}(i)$ at level $l$. Note that $\mathrm{size}(\mathcal{T}(i))=\widehat{\mathrm{size}}(\mathcal{T}(i),0).$ It is easy to check that $\mathrm{span}(\mathcal{T}(i),l)=[i,i+10^{l}-1]$, using induction. We skip the details here.
5. The implementation then becomes a normal routine.

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };


class Solution {
 public:
  int findKthNumber(int n, int k) {
    using int64 = long long;

    const auto D = [n](int acc = 0) mutable {
      while (n > 0) ++acc, n /= 10;
      return acc;
    }();

    auto subtree_size = rec([&](auto&&subtree_size, int64 root, int64 level = 0) -> int64 {
      if (level == 0)
        return 1 + subtree_size(root * 10, level + 1);
      else if (level >= D or root > n)
        return 0;
      else {
        const auto [L, R] = pair(root, root + pow(10, level) - 1);
        if (R <= n)
          return R - L + 1 + subtree_size(root * 10, level + 1);
        else
          return n - L + 1;
        return subtree_size(10 * root, level + 1);
      }
    });

    auto go = rec([&](auto&& go, int64 root, int64 rank) -> int64 {
      if (rank == 1)
        return root;
      else {
        const auto subtree = subtree_size(root);
        if (subtree < rank)
          return go(root + 1, rank - subtree);
        else
          return go(root * 10,  rank - 1);
      }
    });

    return go(1, k);
  }
};