Nth Digit

Problem

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

Examples

Example 1:

1
2
3
4


Input:
n = 3
Output:
 3

Example 2:

1
2
3
4
5


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.

Solution

Method 1 – Digit Length Grouping

Intuition

The sequence is formed by concatenating all positive integers. To find the nth digit, we can group numbers by their digit length (1-digit, 2-digit, etc.), and determine which group and which number within that group contains the nth digit.

Approach

Start with 1-digit numbers, then 2-digit, and so on. For each group, calculate how many digits it contributes.
Subtract the total digits in each group from n until n falls within a group.
Find the exact number and the digit within that number corresponding to n.
Return the digit as an integer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    int findNthDigit(int n) {
        long len = 1, count = 9, start = 1;
        while (n > len * count) {
            n -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }
        start += (n - 1) / len;
        string s = to_string(start);
        return s[(n - 1) % len] - '0';
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func findNthDigit(n int) int {
    length, count, start := 1, 9, 1
    for n > length*count {
        n -= length * count
        length++
        count *= 10
        start *= 10
    }
    start += (n - 1) / length
    s := strconv.Itoa(start)
    return int(s[(n-1)%length] - '0')
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    public int findNthDigit(int n) {
        long len = 1, count = 9, start = 1;
        while (n > len * count) {
            n -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }
        start += (n - 1) / len;
        String s = Long.toString(start);
        return s.charAt((n - 1) % (int)len) - '0';
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    fun findNthDigit(n: Int): Int {
        var len = 1L
        var count = 9L
        var start = 1L
        var nn = n
        while (nn > len * count) {
            nn -= (len * count).toInt()
            len++
            count *= 10
            start *= 10
        }
        start += (nn - 1) / len
        val s = start.toString()
        return s[((nn - 1) % len).toInt()] - '0'
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def findNthDigit(self, n: int) -> int:
        length, count, start = 1, 9, 1
        while n > length * count:
            n -= length * count
            length += 1
            count *= 10
            start *= 10
        start += (n - 1) // length
        s = str(start)
        return int(s[(n - 1) % length])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


impl Solution {
    pub fn find_nth_digit(mut n: i32) -> i32 {
        let (mut len, mut count, mut start) = (1, 9, 1);
        while n > len * count {
            n -= len * count;
            len += 1;
            count *= 10;
            start *= 10;
        }
        start += (n - 1) / len;
        let s = start.to_string();
        s.chars().nth(((n - 1) % len) as usize).unwrap().to_digit(10).unwrap() as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    findNthDigit(n: number): number {
        let len = 1, count = 9, start = 1;
        while (n > len * count) {
            n -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }
        start += Math.floor((n - 1) / len);
        const s = start.toString();
        return Number(s[(n - 1) % len]);
    }
}

Complexity

⏰ Time complexity: O(log n), since the number of digit groups is logarithmic in n.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Solution#

Method 1 – Digit Length Grouping#

Intuition#

Approach#

Code#

Complexity#