400. Nth Digit

// Approach: Identify the digit-length group (1-, 2-, 3-digit numbers…)
// that contains the n-th digit, find the actual number, extract the digit.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int FindNthDigit(int n)
    {
        int digitSize = 1;
        int startNum = 1;
        long count = 9;

        while (digitSize * count < n)
        {
            n -= digitSize * (int)count;
            ++digitSize;
            startNum *= 10;
            count *= 10;
        }

        int targetNum = startNum + (n - 1) / digitSize;
        int index = (n - 1) % digitSize;
        return (int)(targetNum.ToString()[index]) - '0';
    }
}