Nth Digit

How many digits of size size can we have?

1 * 9 (size 1, 1... 9) 2 * 90 (size 2, 10... 99) 3 * 900 (size 3, 100... 999)

So we can "fast-skip" those numbers until we find the size of the number that will hold our digit. At the end of the loop, we will have:

start: first number of size size (will be power of 10)n: will be the number of digits that we need to count after start

How do we get the number that will hold the digit? It will be start + (n - 1) // size (we use n - 1 because we need zero-based index). Once we have that number, we can get the n - 1 % size-th digit of that number, and that will be our result.

class Solution(object): def findNthDigit(self, n): start, size, step = 1, 1, 9 while n > size * step: n, size, step, start = n - (size * step), size + 1, step * 10, start * 10 return int(str(start + (n - 1) // size)[(n - 1) % size])

What is the complexity of this code?

The while loop takes O(log(n)) time because a number n will have at most O(log(n)) digits. Then the return statement takes O(log(n)) time to convert the number to string. So total time complexity is O(log(n)), with O(log(n)) extra space for the string.

Here it's a preliminary O(n) code, that gets TLE but it's useful to start off with during the interview.

class Solution(object): def findNthDigit(self, n): start, size = 1, 1 while n > size: n, start = n - size, start + 1 size = len(str(start)) return int(str(start)[n-1]) class Solution { public: int findNthDigit(int n) { long size = 1, step = 9, start = 1; while(n > size*step){ n -= size*step; ++size; step *= 10; start *= 10; } int num = (n - 1) / size + start; int index = (n - 1) % size; for(int i = 0; i < size - index - 1; ++i) num /= 10; return num % 10; } };