Just explain, no code


  • 3
    W

    sequence 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6
    Nth digital 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

    I list sequence 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
    blow the sequence is the Nth digital, like the 11th digital is 0, 12 is 1, 13 is 1, 14 is 1, 15 is 2, 16 is 1, 17 is 3.........

    Sot ehe regular is very oberviously now:
    1-------9 9*1 = 9 digits
    10-----99 90 *2 = 180 digits
    100---999 900 * 3 = 2700 digits

    Now, for example gave N = 1000, then 1000-9-180 = 811, it means the 811th digit local in [100, 999], and we know each number like 100 has three digit, so 811 / 3 = 270,

    Then, we know the 270th number in [100, 999], is 270th + 100 (start from 100) = 370.

    370 still has three digit, which one is the answer? 3, 7, 0

    811 % 3 = 1, so the first one is the answer, so return 3.


  • 0
    C

    @wzrthhj

    Good explanation.
    810/3=270, 810%3=0 makes the program easy.
    My codes:

    class Solution(object):
        def findNthDigit(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 9:
                return n
                
            bitRange = [ 9*pow(10, i)*(i+1) for i in range(10) ]
            numRange = [ ( pow(10, i), pow(10, i+1)-1 ) for i in range(10) ]
    
            remaining = n
            for i in xrange(len(bitRange)):
                if remaining - bitRange[i] <= 0:
                    return int( str(numRange[i][0] + (remaining-1)/(i+1))[(remaining-1)%(i+1)] )
                    #               base number: 100      270                  0 => 370[0]       
                else:
                    remaining = remaining - bitRange[i]
    

Log in to reply
 

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