k-е число 1..n в словарном порядке

Даны целые n и k, 1 ≤ k ≤ n ≤ 2 147 483 647. Выпишите числа от 1 до n и упорядочьте их как строки в словарном (лексикографическом) порядке: сравнение идёт по цифрам слева направо, а число, с которого начинается другое, стоит перед ним (1, 10, 100, 11, 2, …). Верните число, которое стоит на k-м месте этого порядка (места нумеруются с 1). Выписать и отсортировать все числа не получится: n бывает больше миллиарда.

Пример: 15, 4 → 12 (порядок начинается с 1, 10, 11, 12, 13).

Источник: задача CodeShare