Readable Python solution with comments [35ms]


  • 0
    • Skip whole ranges of numbers having the same digit count
    • Identify the range contains the number we look for
    • Identify the digit
    class Solution(object):
        def findNthDigit(self, n):
            """
            :type n: int
            :rtype: int
            
            Time: O(log n)
            Space: O(1)
            
            """
            # Convert the digit number into zero based index
            n -= 1
            
            # Skip ranges of numbers of same digit count
            # O(log n)
            digits = 1
            skipped_digits = 0
            while 1:
                
                # Range of numbers with the same digit count
                start = 10 ** (digits - 1)
                range_size = 9 * start
                range_digits = digits * range_size
                
                if n < skipped_digits + range_digits:
                    # Found the range which contains the digit we look for
                    break
                
                # Skip the range
                skipped_digits += range_digits
                digits += 1
            
            # Calculate the number which contains the digit
            number_index = n - skipped_digits
            number = start + number_index // digits
            
            # Identify the digit
            digit_index = number_index % digits
            digit = str(number)[digit_index]
            
            # The called expects integer
            return int(digit)
    

Log in to reply
 

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