• 30.1%

https://leetcode.com/problems/nth-digit/description/

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).

1. 找出数字开始的那个数字，如1， 10 ， 100等
2. 找到确切的数字
3. 找到第n个数字，并返回

5ms, September 19, 2016

https://discuss.leetcode.com/topic/59314/java-solution

https://discuss.leetcode.com/topic/59322/sharing-my-thinking-process

Sharing my thinking process

Idea:

The first idea is: the result will only be within 0~ 9, can we find a cycle?

For input 1 to 20, the result is:

1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5

No cycle found. While we can find that digits matter! The result sequence should be like:

1~ 9: 1 * 9=9 in total

10~ 99: 2 * 90=180 in total

100~ 999: 3* 900=2700 in total

Then, 49000, 590000, k910^k

For input 12345, we have 9+180+2700<12345<9+180+2700+36000, so the corresponding number is 1000+.

12345-9-180-2700=9456-1=9455

9455/4 = 2363+1000=3363, 9455%4=3, so the result should be 3. For 12346: 3, for 12347: 3, for 12348: 6, for 12349: 4

336(12345 start from the next 3)3

(12346)3(12347)3(12348)6(12349)4