Nth Digit in infinite integer sequence

Problem: Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Example:

Input:
12

Output:
1

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,... is a 1, which is part of the number 11. Basically rightmost digit of 11.

Approach: Let's count the digits:

• 1 - 9 => 9 digits
• 10 - 99 => 2 * 90 = 180 digits
• 100 - 999 => 3 * 900 = 2700 digits
• 1000 - 9999 => 4 * 9000 = 36000 digits
• ...

100...0 (k digits) - 999...9(k digits) => k * 9 * (10 ^ k) digits

So now we have formula to get the number of digits in all the k digit numbers. We can apply this to our advantage. 

First we need to find lower bound that is minimum integer of k digit where k is the number of digits in n which is 100..0(k digits) say we call it as minKInt. Now we need to find the target integer where nth digit will lie. We can calculate the number of digits till minKInt - 1 using the above formula. (sum of digits from all the 1 digit numbers to (k - 1) digit numbers). Say we call it as digitsdigitsTillNow.

Obviously "n - digitsdigitsTillNow" will tell the number of digits more to calculate and as every integer has k digits, we can say:

targetInteger = minKInt + (n - digitsTillNow) / k

Now we get the target integer. Now we need to find out which digit we are targeting. Given every integer has k digits, we can say:

targetDigit = n % k

So we can return the (targetDigit)th digit from the right of targetInteger. Here there is only one exception where n % k is equal to 0. In that case we just need to return the last digit of targetInteger - 1.

That's all!

Implementation in C#:

        public static int FindNthDigit(int n)

        {

            int x = 9, y = 1;

            long product = x * y;

            while (product < n)

            {

                n -= (int)product;

                x *= 10;

                ++y;

                product = (long)x * (long)y;

            }

            

            // Target Integer

            int targetNumber = ((int)Math.Pow(10, y - 1)) + (n / y);

           

            // Target digit

            n %= y;

            return n == 0 ? (targetNumber - 1) % 10 : (targetNumber.ToString()[n - 1]) - '0';

        }

Complexity: O(logn)