563. K-th Lexicographically Smallest Integer in Range

Given integers n and k, consider all integers from 1 to n sorted in lexicographic (dictionary) order. Return the k-th integer in that order. Use prefix counting to navigate the implicit denary trie. Input: 'n, k'.

Input: 'n, k'.

Output: Integer — the k-th lexicographically smallest integer.

Examples

Input: 13, 2
Output: 10
Explanation: Lex order: 1,10,11,12,13,2,... 2nd is 10.

Input: 1, 1
Output: 1
Explanation: Only one integer.

Input: 100, 10
Output: 17
Explanation: 10th in lexicographic order.

Constraints

• 1<=k<=n<=10^9

Asked by