# Python ''binary search'' solution

• ``````def samelength(m):
# find the number of positive integer i <= m in lexicographical order with len(str(i)) == len(str(m)).
if not m:
return 0
if len(m) == 1:
return int(m)
res = (int(m[0]) - 1)*10**(len(m)-1)
return res + int(m[1:]) + 1

def order(m, n):
# find the rank of m among positive integers no greater then n in lexicographical order.
# here we assume m <= n.
res = 0
for i in range(1, len(m)+1):
res += samelength(m[:i])
if len(n) > len(m) and sum(int(ch) for ch in m)>1:
num = int(n)
mum = int(m)
d = len(n)-len(m)
for i in range(1, d):
m = str(mum*10**i - 1)
res += samelength(m)
m = str(mum*10**d - 1)
res += samelength(min(m, n))
return res

digits = '0123456789'

class Solution(object):
def findKthNumber(self, n, k):
n_str = str(n)
res = ''
while len(res) < len(n_str):
index = order(res + '9', n_str)
if index == k:
return int(res + '9')
elif index < k:
res += '9'
continue
else:
lo, hi = 0, 9
while lo + 1 < hi:
mid = (lo + hi)//2
index = order(res + digits[mid], n_str)
if index <= k:
lo = mid
else:
hi = mid
res += digits[lo]
if order(res, n_str) == k:
return int(res)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.