Leetcode: Nth Digit

Nth Digit



Similar Problems:


Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

Input:
3

Output:
3

Example 2:

Input:
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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/nth-digit
// Basic Ideas: math
//             len   count   start
//  1-9         1     9        1
//  10-99       2     90       10
//  100-999     3     900      100
//
// Let's say n=200
// Starting from 1000, we need to find 11th digit of the sequence [100, 101, 102, 103, ..]  
//     11 = 200-(9+2*90)
//     So we should check 103. (100 + (11-1)/3)
//     Then (11-1)%3 digit, which is 0 in 103.
// Complexity: Time O(log(n)), Space O(1)
import "strconv"
func findNthDigit(n int) int {
    len, count, start := 1, 9, 1
    for n > len*count {
        n -= len*count
        len++
        count *= 10
        start *= 10
    }
    value := strconv.Itoa(start + (n-1)/len)
    res, _ := strconv.Atoi(string(value[(n-1)%len]))
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.