400. Nth Digit

Time: O(log n)

Space: O(1)

Intuition

Digits are grouped by number of digits: 1-digit (1 - 9, 9 numbers, 9 digits total), 2-digit (10 - 99, 90 numbers, 180 digits), etc. Find which group the n-th digit falls in, then the exact number, then the exact digit within that number.

Algorithm

1digits=1, count=9, start=1.
2While n > digits*count: n -= digits*count. digits++. count*=10. start*=10.
3The target number is start + (n-1)/digits.
4The digit within that number: (n-1) % digits, counted from the left.

Example Walkthrough

Input: n = 11

1.Group 1 (1-digit): 9 digits. n=11>9 -> n=2, digits=2, start=10.
2.Number = 10 + (2-1)/2 = 10. Digit index = (2-1)%2 = 1. "10"[1] = "0".

Output: 0

Common Pitfalls

•Subtract group total from n before advancing - the remaining n indexes within the next group.

400.cs

// 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';
    }
}

Was this solution helpful?