Scale Engineer

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 nth 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 <= 231 - 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:

  1. num=1, s="1", len=1. 11 > 1. n becomes 11-1=10.
  2. num=2, s="2", len=1. 10 > 1. n becomes 10-1=9. ...
  3. num=9, s="9", len=1. 3 > 1. n becomes 2.
  4. num=10, s="10", len=2. 2 <= 2. The digit is in "10". It's the (2-1)=1st character, which is '0'.
class Solution {    public int findNthDigit(int n) {        // This approach is too slow and will cause Time Limit Exceeded for large n.        int num = 1;        while (true) {            String s = Integer.toString(num);            int len = s.length();            if (n <= len) {                return Character.getNumericValue(s.charAt(n - 1));            }            n -= len;            num++;        }    }}

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.

Solutions

public class 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 num.ToString()[idx] - '0';    }}

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 →

Next problem