Leetcode 400. Nth Digit

Problem Explanation

The question asks us to figure out the digit which is in the nth position in a sequentially arranged string. So if we're handing over 'n' as an integer to our function, it will return the 'nth' digit in the sequence of natural numbers from 1 to infinity put together.

"3" would return '3', as it's the third digit in the string: '12345678910...' "11" would return '0', as '0' is the 11th digit in the infinity string: '1234567891011...'

We must note, however, that the function should work with very large numbers of 'n' - it should be able to handle any 32-bit signed integer.

Approach

The main idea is to find the actual number that contains the nth digit and its corresponding digit position. In order to do so, we need to know how many digits are there within a number range. For instance, there are 9 one-digit numbers, 90 two-digit numbers, 900 three-digit numbers, and so on. On encountering such digit lengths in increasing order, we can skip blocks of numbers until we reach the one containing the target nth digit.

We traverse the ranges until we figure out the range where the nth digit is. For example, if n = 189, we first subtract 91, then 902, and we know that the 189th digit is in the third range. We figure out the actual number using digitSize, and finally, we find out the exact digit in that number.

Let's walk through our approach with an example: n = 15

The 15th digit of the sequence 1, 2, 3, ..., 9, 10, 11, 12, 13... is found in the range of two-digit numbers, ie., between 10 and 99. Hence, 'digitSize' is 2 and 'startNum' is 10. 'n' is decremented by the count of digits until it reaches the range containing the nth digit. Here, 'n' becomes 6 (15-9). Finally, we locate the number having the nth digit (startNum+(n−1)/digitSize) and the index of the nth digit in that number (n−1)%digitSize.

Python Solution

1
2python
3class Solution:
4    def findNthDigit(self, n: int) -> int:
5        digitSize = 1
6        startNum = 1
7        count = 9
8
9        while n > digitSize * count:
10            n -= digitSize * count
11            digitSize += 1
12            startNum *= 10
13            count *= 10
14
15        startNum += (n - 1) // digitSize
16        return int(str(startNum)[(n - 1) % digitSize])

Java Solution

1
2java
3class Solution {
4    public int findNthDigit(int n) {
5        int digitSize = 1;
6        long startNum = 1;
7        long count = 9;
8
9        while (digitSize * count < n) {
10            n -= digitSize * count;
11            digitSize++;
12            startNum *= 10;
13            count *= 10;
14        }
15
16        int targetNum = (int) (startNum + (n - 1) / digitSize);
17        int index = (n - 1) % digitSize;
18        return Integer.parseInt(Integer.toString(targetNum).substring(index, index + 1));
19    }
20}

JavaScript Solution

1
2javascript
3var findNthDigit = function(n) {
4    let digitSize = 1;
5    let startNum = 1;
6    let count = 9;
7
8    while(n > digitSize * count){
9        n -= digitSize * count;
10        digitSize++;
11        startNum *= 10;
12        count *= 10;
13    }
14
15    startNum += (n - 1) / digitSize;
16    return String(startNum)[(n - 1) % digitSize];
17};

C++ Solution

1
2c++
3class Solution {
4public:
5    int findNthDigit(int n) {
6        int digitSize = 1;
7        long startNum = 1;
8        long count = 9;
9
10        while (digitSize * count < n) {
11            n -= digitSize * count;
12            digitSize++;
13            startNum *= 10;
14            count *= 10;
15        }
16
17        int targetNum = startNum + (n - 1) / digitSize;
18        int index = (n - 1) % digitSize;
19        return to_string(targetNum)[index] - '0';
20    }
21};

C# Solution

1
2CSharp
3public class Solution {
4    public int FindNthDigit(int n) {
5        int digitSize = 1;
6        long count = 9;
7        int startNum = 1;
8
9        while (n > digitSize * count) {
10            n -= (int) (digitSize * count);
11            digitSize += 1;
12            startNum *= 10;
13            count *= 10;
14        }
15        
16        startNum += (n - 1) / digitSize;
17        string s = startNum.ToString();
18        return (int)Char.GetNumericValue(s[(n - 1) % digitSize]);
19    }
20}

Ruby Solution

The Ruby solution is also very similar to the given Python, Java, JavaScript, and C++ solutions. You start by initialising digitSize = 1, startNum = 1, and count = 9. Then you use a while loop to decrease n until it is less than digitSize * count. After finding the range containing the nth digit, you locate the number that has the nth digit and find the index of the nth digit in that number. Here is the Ruby solution code:

1
2ruby
3def findNthDigit(n)
4    digitSize = 1
5    startNum = 1
6    count = 9
7
8    while n > digitSize * count
9        n -= digitSize * count
10        digitSize += 1
11        startNum *= 10
12        count *= 10
13    end
14
15    startNum += (n - 1) / digitSize
16    return startNum.to_s[(n - 1) % digitSize].to_i
17end

This will return the nth digit of the infinite integer array.

Go Solution

Here, the Go solution is also provided which is similar to the solutions of other languages. Firstly, you start by initialising the variables digitSize, startNum and count to 1, 1, and 9 respectively. After that, you decrease the value of 'n' until it's less than 'digitSize * count'. Then you try to find the range in which 'n'th digit is. Find the exact number that contains 'n'th digit and finally find the 'n'll digit's index in that number.

1
2go
3func findNthDigit(n int) int {
4    digitSize := 1
5    startNum := 1
6    count := 9
7
8    for n > digitSize*count {
9        n -= digitSize * count
10        digitSize++
11        startNum *= 10
12        count *= 10
13    }
14
15    startNum += (n - 1) / digitSize
16    return int(strconv.Itoa(startNum)[(n-1)%digitSize] - '0')
17}

This function returns the n'th digit of the number sequence from 1 to infinity as an integer.