Nth Digit

MEDIUM

Description

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 11^th 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

Checkout 2 different approaches to solve Nth Digit. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Simulation

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.

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'.

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 Analysis

Time Complexity: 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 Complexity: O(log N). The space is dominated by storing the string representation of the current number, which has a length of `O(log N)`.

Pros and Cons

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.

Code Solutions

Checking out 5 solutions in different languages for Nth Digit. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Nth Digit

Algorithms:

Binary Search

Patterns:

Math

Companies:

Accenture |