Input:
3

Output:
3

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.

public class Solution {
    public int findNthDigit(int n) {
        long base = 9;
        int width = 1;
        long count = 0; //number of digits already before the start the the range
        int start = 1; //start number of the range
        while (n > count + base * width) {
            count += base * width;
            base = base * 10;
            width ++;
            start = start * 10;            
        }
        int diff = (int)(n - count - 1);
        int number = start + diff / width;
        int offset = width - diff % width - 1;
        for (int i = 0; i < offset; i ++) {
            number = number / 10;
        }
        return number % 10;
    }
}