aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_lexicographical.py
diff options
context:
space:
mode:
Diffstat (limited to 'kth_smallest_lexicographical.py')
-rw-r--r--kth_smallest_lexicographical.py36
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))