400. Nth Digit

  • 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.

方法一:

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

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int findNthDigit(int n) {
int len = 1;
int start = 1;
// 如果是int就会答案错误,
// 所以涉及数字较大,一定要用long,long long
long cnt = 9;

while(n>len*cnt){
n -= len*cnt;
len++;
cnt *= 10;
start *= 10;
}
start += (n-1)/len;
string num = to_string(start);
return num[(n-1)%len] - '0';
}
};

5ms, September 19, 2016

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int findNthDigit(int n) {
int len = 1;
long count = 9;
int start = 1;

while(n > len*count){
n -= len*count;
len += 1;
count *= 10;
start *= 10;
}

start += (n-1) / len;
String s = Integer.toString(start);
return Character.getNumericValue(s.charAt((n-1)%len));
}
}

方法二:

简单直接的方法,但是超时

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int findNthDigit(int n) {
string s;
int i = 1;
while(n>s.size()){
s.append(to_string(i));
++i;
}
return s[n-1]-'0';
}
};

学习区:

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

谢谢你,可爱的朋友。