Problem statement

https://leetcode.com/problems/nth-digit/

Solution

There will be 9 numbers with 1 digit, 90 numbers with 2 digits, 900 numbers with 3 digits and so on. So, given n, first we subtract 1*9, then 2*90, 3*900, till it is possible. Let us have number m after subtractions and d digits. Then our number is 10^{d-1} + (m-1)//d and digit is (m-1)% d in this number (starting with zero).

Complexity

Complexity is O(log n) time and O(1) space.

Code

class Solution:
    def findNthDigit(self, n):
        block, d = 9, 1
        while n > d*block:
            n -= d*block
            block *= 10
            d += 1
            
        num = 10**(d-1) + (n - 1)//d
        place = (n - 1) % d
        return int(str(num)[place])