# Question

Formatted question description: https://leetcode.ca/all/400.html

 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.


# Algorithm

Define a variable cnt, initialize it to 9, and then expand by 10 times each loop, and use a variable len to record the number of digits in the current loop interval, and another variable start is needed to record the current loop interval The first number.

We subtract len*cnt (the total number of digits in the interval) every time we loop. When n falls into a certain interval, then (n-1)/len is the coordinate of the target number in that interval, plus The start is to get the target number, and then we convert the target number start into a string, (n-1)%len is the required target bit.

Finally, don’t forget to consider the int overflow problem.

Java