Title: Nth DigitSource: leetcode.com
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Python solution
The intuition for the solution is thinking about what’s the count of numbers having d digits.
For example, there are 9 numbers (1-9) having 1 digit, 90 numbers (10-99) having 2 digits and so on.
Once we have this, we know how many digits are there in each range of numbers. Based on that we find the numbers which would have the required digit.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
''' https://leetcode.com/problems/nth-digit/''' class Solution(object): def findNthDigit(self, n): """ :type n: int :rtype: int """ import math #maxInt = 2147483648 if n < 10: return n n = n - 9 # counts of integers of 1,2,3 etc. digit counts d = { 1 : 9, # not to be used. Only for reference 2 : 90, 3 : 900, 4 : 9000, 5 : 90000, 6 : 900000, 7 : 9000000, 8 : 90000000, 9 : 900000000 } i = 2 digits = i * d[i] while n > digits: n -= digits i += 1 digits = i * d[i] # Defines the number to be used div = int(math.ceil(n / float(i))) # Defines the digit within number to be used mod = n % i x = int("9" * (i-1)) # Holds the actual number which contains required digit num = x + div # Index of the digit within number index = mod - 1 return int(str(num)[index]) |