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.

Difficulty: interview

Starter code:

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

Solutions:
class Solution(object):
     def findKthNumber(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: int
         """
         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:
             #calculate how many numbers between current value and current value + 1
             count = self.countNumber(res,res + 1,n)
             if k >= count:
                 #result >= res +1
                 k -= count
                 res += 1
             else:
                 #res*10 <= result < res + 1
                 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):
         """
         :type n: int
         :type k: int
         :rtype: int
         """
         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
 
 
 


class Solution:
     def findKthNumber(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: int
         """
         curr=1
         k=k-1
         
         def calSteps(n,n1,n2):
             steps=0
             while n1<=n:
                 
                 
                 steps+=min(n+1,n2)-n1
                 
                 
                 n1*=10
                 n2*=10
             return steps
         
         while k>0:
             steps=calSteps(n,curr,curr+1)
             
             if steps<=k:
                 k-=steps
                 curr=curr+1
             else:
                 curr*=10
                 k=k-1
         return curr