Quickly determine the region of the input value


  • 0
    A

    Code at the end of the text

    1,2,3,4,5,6,7,8,9,10,11,12…………
    The above sequence can be divided into N regions
    1~9, 10~99, 100~999, …………(10^(n-1))~((10^n) - 1)

    The number of digits in each area is as follows
    1x9, 2x90, 3x900, 4x9000,…………n9(10^n)

    The total digits length of 1 to N regions is as follows
    9*(1 + 20 + 300 + 4000 ………… + n*(10^n))

    when N = 9
    9*(1 + 20 + 300 + 4000 ………… + n*(10^n)) = 9*(987654321)
    when N = 13
    9*(1 + 20 + 300 + 4000 ………… + n*(10^n)) = 9*(13121110987654321)
    (The numbers in parentheses are very interesting,After the reversal is 1 2 3 4 5 6 7 8 9 10 11 12 ………… n)

    When the input data is the maximum value(2^31)
    2^31 = 9*(238609294.2222222) < 9*(987654321)
    So we can divide the input number by the value of 9 to determine which region he is in
    e.g. input 1000
    1000//9 = 111 #the length of 111 is 3, so it belongs to the third or forth region
    because 111 < 321 so it belongs to the second region

    e.g. input 3269875
    3269875//9 = 363319 #the length of 363319 is 6, so it belongs to the sixth or seventh region
    because 363319 < 654321 so it belongs to the sixth region

    #Because just learning programming soon, the code is not beautiful ( ゜- ゜)つロ
    class Solution(object):
    def findNthDigit(self, n):
    """
    :type n: int
    :rtype: int
    """

        reverse = 0
        sum = 0
        divideBy9 = n // 9
        region = len(str(divideBy9))
        for i in range(region):
            reverse = (region - i) + reverse * 10 #build a num such as 65421 which length is region
    
        if divideBy9 > reverse:
            region += 1
        if divideBy9 == reverse and n % 9 > 0:
            region += 1
            for i in range(region):
                reverse = (region - i) + reverse * 10 #build a num such as 65421 which length is (region - 1)
    
        for i in range(region - 1):
            sum = (region - i - 1) + sum * 10
        sum *= 9
        start = pow(10, region - 1)
        delta = n - sum
        offset = delta % region - 1
        targetPlace = start + delta // region
        if offset < 0:
            offset = region - 1
            targetPlace -= 1
        targetBit = str(targetPlace)[offset]
        return int(targetBit)

Log in to reply
 

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