Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Note: 1 ≤ k ≤ n ≤ 109.

Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Starter code: class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        

Solutions:
class Solution(object):

	def findKthNumber(self, n, k):
		(s, nn) = (0, str(n))
		while nn:
			if not k:
				return s
			(c, m) = (0, 10 ** (len(nn) - 1))
			(mm, p, t) = ((m - 1) // 9, int(nn) // m, 0)
			for i in range(1 if not s else 0, p):
				cc = c + m + mm
				if cc >= k:
					s = 10 * s + i
					k -= c + 1
					nn = '9' * (len(nn) - 1)
					t = 1
					break
				c = cc
			if not t:
				cc = c + int(nn) - m * p + 1 + mm
				if cc >= k:
					s = 10 * s + p
					k -= c + 1
					nn = nn[1:]
				else:
					c = cc
					for i in range(p + 1, 10):
						cc = c + mm
						if cc >= k:
							s = 10 * s + i
							k -= c + 1
							nn = '9' * (len(nn) - 2)
							break
						c = cc
		return s


class Solution:

	def findKthNumber(self, n, k):
		self.d = {}
		res = 1
		k -= 1
		while k > 0:
			count = self.countNumber(res, res + 1, n)
			if k >= count:
				k -= count
				res += 1
			else:
				k -= 1
				res *= 10
		return res

	def countNumber(self, l, r, maxValue):
		if l > maxValue:
			return 0
		if (l, r) in self.d:
			return d[l, r]
		res = min(maxValue + 1, r) - l
		l *= 10
		r *= 10
		res += self.countNumber(l, r, maxValue)
		self.d[l, r] = res
		return res


class Solution:

	def findKthNumber(self, n, k):
		cur = 1
		k -= 1
		while k > 0:
			steps = self.calSteps(n, cur, cur + 1)
			if steps <= k:
				cur += 1
				k -= steps
			else:
				cur *= 10
				k -= 1
		return cur

	def calSteps(self, n, n1, n2):
		steps = 0
		while n1 <= n:
			steps += min(n + 1, n2) - n1
			n1 *= 10
			n2 *= 10
		return steps