9 Lines Python Solution with detailed explanation


  • 1

    Key idea: n-digit numbers occupied 9n(10^n-1) digits.

    Say n-th digit is belong to number x: (for example, 14th digit (1) is belong to 12)

    1. Get x's length. (how many digits does x have?)
    2. Get the beginning position and beginning number of such length (e.g. 10 is start position of 2-digit number)
    3. Get x's value, and also the corresponding digit, based on 1 and 2.
    4. Output the desired digit
    class Solution(object):
        def findNthDigit(self, n):
            if n <= 9: return n
            startpos, tmp, dgt = 0, n, 0
            while tmp > 0:                       # part 1
                span = (dgt+1)*9*(10**dgt)
                tmp, startpos, dgt = tmp-span, startpos+span, dgt+1
    
            dgt -= 1                                # part 2
            startpos, start = startpos-span, 10**(dgt)
    
            tgt, rmd = ((n-startpos)/(dgt+1))+start, (n-startpos)%(dgt+1)    # part 3
    
            return int(str(tgt)[rmd-1]) if rmd != 0 else int(str(tgt-1)[rmd-1])

Log in to reply
 

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