Sharing my thinking process


  • 14

    Idea:

    The first idea is: the result will only be within 0~9, can we find a cycle?

    For input 1 to 20, the result is:

    1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5

    No cycle found. While we can find that digits matter! The result sequence should be like:

    1~9: 1*9=9 in total

    10~99: 2*90=180 in total

    100~999: 3*900=2700 in total

    Then, 49000, 590000, k910^k

    For input 12345, we have 9+180+2700<12345<9+180+2700+36000, so the corresponding number is 1000+.

    12345-9-180-2700=9456-1=9455

    9455/4 = 2363+1000=3363, 9455%4=3, so the result should be 3. For 12346: 3, for 12347: 3, for 12348: 6, for 12349: 4

    336(12345 start from the next 3)3

    (12346)3(12347)3(12348)6(12349)4


  • 0

    While I didn't get the concise solution as the first post of this problem. :(


  • 0
    This post is deleted!

  • 1

    Why should 9456 minus 1 to be 9455? If the index if 1000 is 0 so that index of 12345th number should be 9455,right?


  • 1

    Based on your thinking process, I write the code and it accepts, beats 86.13%.

    class Solution(object):
        def findNthDigit(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 10:
                return n
            buff = [0,9,180,2700,36000,450000,5400000,63000000,720000000,8100000000]
            temp = n
            pos = 0
            for i in xrange(0,len(buff)):
                temp -= buff[i]
                if temp < 0:
                    pos = i
                    temp += buff[i]
                    break
            div = temp/pos
            remainder = temp%pos
            result = pow(10,pos-1) + (div-1)
            if remainder == 0 :
                return int(str(result)[-1])
            else:
                return int(str(result+1)[remainder-1])
    

Log in to reply
 

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