946. Kth Smallest in Lexicographic Order

Given integers n and k, consider all integers from 1 to n sorted in lexicographic (dictionary) order and return the k-th one. Navigate the implicit denary trie using prefix counting. The input is 'n k'.

Input: 'n k' (two integers).

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