Python ''binary search'' solution


  • 0
    K
    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)
    

Log in to reply
 

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