Description
A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows: 11212312341234512345612345671234567812345678912345678910123456789101112345678910
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)
Output
There should be one output line per test case containing the digit located in the position i.
Sample Input
2 8 3
Sample Output
2 2
网站链接
#include <iostream>
#include <math.h>
using namespace std;
// 设 t(n) 表示为 123~n 的位数
// 则有 f(n) = f(n-1) + t(n)
int length = 80000;
int tn[80000];
// 计算一个数字的长度，比如 12345678，则返回8
int getLength(int num) {
int length = 0;
while (num/10 != 0) {
num/=10;
length++;
}
return length + 1;
}
// 统一计算 tn[] 的值
void calculationTn() {
tn[0] = 0;
tn[1] = 1;
for (int i =1; i < length; i++) {
tn[i] = tn[i - 1] + getLength(i);
}
}
// 计算该数字的第 index 位的数字，比如 12345678 第三位数，则返回 3（number、index 必须大于 0）
int getNumFromIntegerByIndex(int number, int index) {
int length = getLength(number);
for (int i = 0; i < length - index; i++) {
number/=10;
}
return number%10;
}
// 从123456789101112..中查找第 index 个数
int findFromNumber(int index) {
for (int t = 1; t < length; t++) {
if (index <= tn[t]) {
return getNumFromIntegerByIndex(t, index - tn[t - 1]);
}
}
return 0;
}
// 从完整数列（1 12 123 1234 12345 ....）中查找第 index 未数
int findFromWhole(int index) {
for(int i = 1; i < length; i++) {
if (index > tn[i]) {
index -= tn[i];
} else if (index < tn[i]) {
return findFromNumber(index);
} else {
//number == tn[i]
return getNumFromIntegerByIndex(i, getLength(i));
}
}
return 0;
}
int main(int argc, const char * argv[]) {
calculationTn();
int n, num;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &num);
printf("%d\n", findFromWhole(num));
}
}
