Nth Digit

Med

#0387Time: O(N). To find the Nth digit, the loop iterates through approximately `N / log10(N)` numbers. Inside the loop, converting a number `i` to a string takes `O(log10(i))` time. The total complexity is roughly the sum of `log10(i)` for `i` up to `N/logN`, which is approximately `O(N)`. This will result in a 'Time Limit Exceeded' error for large N.Space: O(log N). The space is dominated by storing the string representation of the current number, which has a length of `O(log N)`.1 company

Patterns

Math

Algorithms

Binary Search

Companies

Accenture

Prompt

Given an integer n, return the n^th digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Example 1:

Input: n = 3
Output: 3

Example 2:

Input: n = 11
Output: 0
Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

Constraints:

1 <= n <= 2³¹ - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the creation of the infinite integer sequence [1, 2, 3, ...] digit by digit. We iterate through numbers, and for each number, we check if the nth digit falls within its string representation.

Algorithm

Initialize a counter num = 1.
Start an infinite loop.
Convert num to its string representation s.
Get the length of the string, len.
If n is less than or equal to len, the target digit is within the current number. Return the digit at index n-1 of s.
Otherwise, subtract len from n and increment num to proceed to the next number.

Walkthrough

The most intuitive way to solve this problem is to simulate the process directly. We can generate the sequence of numbers starting from 1 and keep track of the total number of digits seen so far.

The algorithm proceeds as follows:

Start with the number i = 1.
In a loop, convert the current number i to its string representation.
Let the length of this string be len.
If our target index n is less than or equal to len, it means the digit we are looking for is within the current number i. The desired digit is the (n-1)th character of the string.
Otherwise, the digit is in a subsequent number. We subtract len from n to move our target index forward and increment i to consider the next number.
This process continues until the nth digit is found.

For example, if n = 11:

num=1, s="1", len=1. 11 > 1. n becomes 11-1=10.
num=2, s="2", len=1. 10 > 1. n becomes 10-1=9. ...
num=9, s="9", len=1. 3 > 1. n becomes 2.
num=10, s="10", len=2. 2 <= 2. The digit is in "10". It's the (2-1)=1st character, which is '0'.

1class Solution {2    public int findNthDigit(int n) {3        // This approach is too slow and will cause Time Limit Exceeded for large n.4        int num = 1;5        while (true) {6            String s = Integer.toString(num);7            int len = s.length();8            if (n <= len) {9                return Character.getNumericValue(s.charAt(n - 1));10            }11            n -= len;12            num++;13        }14    }15}

Complexity

Time

O(N). To find the Nth digit, the loop iterates through approximately `N / log10(N)` numbers. Inside the loop, converting a number `i` to a string takes `O(log10(i))` time. The total complexity is roughly the sum of `log10(i)` for `i` up to `N/logN`, which is approximately `O(N)`. This will result in a 'Time Limit Exceeded' error for large N.

Space

O(log N). The space is dominated by storing the string representation of the current number, which has a length of `O(log N)`.

Trade-offs

Pros

Conceptually simple and easy to implement.
Correct for small values of n.

Cons

Extremely inefficient for large values of n as specified in the constraints.
Will not pass the time limits on most platforms.

This efficient approach avoids simulation by mathematically determining which number contains the nth digit and then pinpointing the digit itself. It works by analyzing the number of digits for numbers of different lengths (1-digit, 2-digit, etc.).

Algorithm

Initialize variables: digits = 1, count = 9 (number of d-digit numbers), start = 1 (the first d-digit number).
Use a while loop to find the correct group of numbers (e.g., 1-digit, 2-digit, etc.). The loop continues as long as n is larger than the total number of digits in the current group (digits * count).
Inside the loop, update n by subtracting the digits of the processed group. Then, increment digits and update count and start for the next group (e.g., count *= 10, start *= 10).
After the loop, n represents the 1-based index of the digit within the current group.
Calculate the target number: num = start + (n - 1) / digits.
Calculate the 0-based index of the digit within the number: index = (n - 1) % digits.
Convert num to a string and extract the character at index.
Convert the character to an integer and return it.

Walkthrough

Instead of generating the sequence, we can deduce the location of the nth digit by observing the pattern of how many digits are contributed by numbers of a certain length.

1-digit numbers (1-9): 9 numbers × 1 digit/number = 9 digits
2-digit numbers (10-99): 90 numbers × 2 digits/number = 180 digits
3-digit numbers (100-999): 900 numbers × 3 digits/number = 2700 digits
In general, d-digit numbers: 9 * 10^(d-1) numbers × d digits/number.

The algorithm has three main steps:

Find the number of digits (digits) of the target number. We loop, subtracting the total digits for each group (1-digit numbers, 2-digit numbers, etc.) from n until n falls within the range of the current group.
Find the specific number (num) that contains the digit. Once we know the number of digits (digits), the remaining value of n tells us how far into that group the digit is. The target number can be calculated as start_number + (n - 1) / digits.
Find the actual digit. The index of the digit within the target number is given by (n - 1) % digits. We can then extract this digit from the number.

Let's trace with n = 11:

Step 1: The digit is not in a 1-digit number (since 11 > 9). We subtract 9 from n, so n becomes 2. We now look for the 2nd digit among all 2-digit numbers.
Step 2: The numbers are 2-digit (digits = 2). The first 2-digit number is 10 (start = 10). The target number is 10 + (2 - 1) / 2 = 10 + 0 = 10.
Step 3: The index of the digit within the number 10 is (2 - 1) % 2 = 1. The digit at index 1 of "10" is '0'.

It's crucial to use long for intermediate calculations involving the count of numbers to prevent integer overflow, as n can be large.

1class Solution {2    public int findNthDigit(int n) {3        // Use long to prevent overflow, as count can become large4        long count = 9;5        int digits = 1;6        long start = 1;7 8        // 1. Find the length of the number where the nth digit is9        while (n > digits * count) {10            n -= digits * count;11            digits++;12            count *= 10;13            start *= 10;14        }15 16        // 2. Find the actual number17        // n is now 1-based index within the current digit-length group18        long num = start + (n - 1) / digits;19 20        // 3. Find the digit within the number21        // (n - 1) % digits gives the 0-based index of the digit22        String s = Long.toString(num);23        char digitChar = s.charAt((n - 1) % digits);24        25        return Character.getNumericValue(digitChar);26    }27}

Complexity

Time

O(log N). The `while` loop runs at most about 9-10 times for `N` up to `2^31 - 1`, as the number of digits in `N` is `O(log10(N))`. All other operations (arithmetic, string conversion) also take time proportional to the number of digits, so the overall complexity is logarithmic.

Space

O(log N). This space is used to store the string representation of the target number. Since the number of digits in the target number is `O(log N)`, the space complexity is logarithmic. This is often considered O(1) constant space as it's very small.

Trade-offs

Pros

Highly efficient and fast, easily passing time limits for large n.
Scales well with even larger inputs.

Cons

The logic is more complex than the brute-force approach.
Requires careful handling of integer types to avoid overflow (using long is recommended).

Solutions

Solution

1public class Solution {2    public int FindNthDigit(int n) {3        int k = 1, cnt = 9;4        while ((long) k * cnt < n) {5            n -= k * cnt;6            ++k;7            cnt *= 10;8        }9        int num = (int) Math.Pow(10, k - 1) + (n - 1) / k;10        int idx = (n - 1) % k;11        return num.ToString()[idx] - '0';12    }13}

1class Solution { public int findNthDigit ( int n ) { int k = 1 , cnt = 9 ; while (( long ) k * cnt < n ) { n -= k * cnt ; ++ k ; cnt *= 10 ; } int num = ( int ) Math . pow ( 10 , k - 1 ) + ( n - 1 ) / k ; int idx = ( n - 1 ) % k ; return String . valueOf ( num ). charAt ( idx ) - '0' ; } }

1/** * @param {number} n * @return {number} */ var findNthDigit = function (n) {2  let k = 1,3    cnt = 9;4  while (k * cnt < n) {5    n -= k * cnt;6    ++k;7    cnt *= 10;8  }9  const num = Math.pow(10, k - 1) + (n - 1) / k;10  const idx = (n - 1) % k;11  return num.toString()[idx];12};

1class Solution { public: int findNthDigit ( int n ) { int k = 1 , cnt = 9 ; while ( 1ll * k * cnt < n ) { n -= k * cnt ; ++ k ; cnt *= 10 ; } int num = pow ( 10 , k - 1 ) + ( n - 1 ) / k ; int idx = ( n - 1 ) % k ; return to_string ( num )[ idx ] - '0' ; } };

1class Solution : def findNthDigit ( self , n : int ) -> int : k , cnt = 1 , 9 while k * cnt < n : n -= k * cnt k += 1 cnt *= 10 num = 10 ** ( k - 1 ) + ( n - 1 ) // k idx = ( n - 1 ) % k return int ( str ( num )[ idx ])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem