diff options
Diffstat (limited to 'kth_smallest_lexicographical.py')
-rw-r--r-- | kth_smallest_lexicographical.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/kth_smallest_lexicographical.py b/kth_smallest_lexicographical.py new file mode 100644 index 0000000..8f56678 --- /dev/null +++ b/kth_smallest_lexicographical.py @@ -0,0 +1,36 @@ +# 440. K-th Smallest in Lexicographical Order + +""" +given two integers 'n' and 'k', return the k'th lexicographically smallest +integer +""" + + +class Solution(object): + def findKthNumber(self, n, k): + """ + :type n: int + :type k: int + :rtype: int + """ + curr = 1 + k -= 1 + while k > 0: + cnt = 0 + interval = [curr, curr + 1] + while interval[0] <= n: + cnt += min(n + 1, interval[1]) - interval[0] + interval = [10 * interval[0], 10 * interval[1]] + if k >= cnt: + curr += 1 + k -= cnt + else: + curr *= 10 + k -= 1 + return curr + + +if __name__ == "__main__": + obj = Solution() + print(obj.findKthNumber(13, 2)) + print(obj.findKthNumber(1, 1)) |