# Easy Understanding Python 49ms Solution

• 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
``````

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