Easy Understanding Python 49ms Solution


  • 0

    Inspired from this post by @xialanxuan1015 .

    The basic idea is: find the digit of result, from left to right.

    e.g.  Say n = 333, k = 171
    breakdown n into 9 buckets: [111, 111, 45, 11, 11, 11, 11, 11, 11].
                                   1    2   3   4   5   6   7   8   9      => digit = 2
    breakdown 110 into 10 buckets: [11, 11, 11, 11, 11, 11, 11, 11, 11, 11].
    (-1 for top element)             0   1   2   3   4   5   6   7   8   9 => digit = 5
    breakdown 10 into 10 buckets: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1].
                                   0  1  2  3  4  5  6  7  8  9            => digit = 2
    ans = 252.
    

    Explanation:

    1. Get the bucket-size of n numbers distributed into 9 buckets (represent 1 - 9) and find out k-th number falls in which one (say, bucket B).
    2. Break down bucket B into 10 buckets (represent 0 - 9), get the bucket-size of and find out k-th number falls in which one.
    3. Repeat 2. until no more numbers

    Here's my Python code:

    class Solution(object):
        def findKthNumber(self, n, k):
            if n <= 9 or k == 1: return k
            init, res, sumOfBkts, bktID = 1, 0, [n], 0
    
            while k > 0:
                k = k-1
                sumOfBkts = self.getBucket(sumOfBkts[bktID], init)
                bktID, k = self.findDigit(sumOfBkts, k)
                res = res*10+(bktID+init) if bktID != 10 else res+1
                init = 0
            return res
    
        def getBucket(self, togo, init=False):                  # generate buckets
            if not init: togo -= 1
            L = 9 if init else 10
            newBkt, num, b = [0 for _ in xrange(L)], 1, 0      # num: numbers in this layer  
            while togo > 0:
                add = num if togo-num > 0 else togo             # add the rest numbers into buckets
                newBkt[b], togo, b = newBkt[b]+add, togo-num, b+1
                if b == L: num, b = num*10, 0
            return newBkt
    
        def findDigit(self, sumBkt, k, bktId=0):                # find out which bucket.
            while k-sumBkt[bktId] >= 0: k, bktId = k-sumBkt[bktId], bktId+1      # go next bucket
            return bktId, k
    

Log in to reply
 

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