2013
11-08

# Number Sequence

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

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)

There should be one output line per test case containing the digit located in the position i.

2
8
3

2
2

//* @author:

public class Main {

//求数 n 的位数
public static int getWeiShu(int n)
{
int weiShu = 0;
while(n != 0)
{
n = n/10;
weiShu++;
}
return weiShu;
}

public static int location(int i)
{
//i - 所求序数
//ans - 所求位的数字
//j - 递推定位串
//base - 记录每个串递增的位数
//sum - 记录串的总位数 、 用作计数

int ans;
int j = 1, base, sum = 1;
while(i >= sum)
{
i -= sum;
j++;    //j 记载 下一个串 到哪个数字串了 -- 12...j
base = getWeiShu(j);
//该串比上一个串多的字符数 -  j 的位数
sum += base;        //该串的字符总数
}
//出口：i >= 0
if( i == 0)
{
ans = (j -1) % 10;
return ans;
}

sum = 1;  //从串(1...j) 中第一个数开始找
base = 1;  //串中第一个数的位数是 1
while( i >= base)  //求 1...j 串中第 i 个数字
{
i -= base;
sum++;
base = getWeiShu(sum);  //sum 的位数
}

if( i == 0)
{
ans = (sum -1) % 10;
return ans;
}

j = getWeiShu(sum) - i;
while( j-- > 0)  //ans is the ith number of (sum)
{
sum /= 10;
}
ans = sum % 10;
return ans;
}

public  static void main(String[] args)
{

java.util.Scanner input = new java.util.Scanner(System.in);
int t = input.nextInt();  //test number

while(t-- > 0)
{
int i = input.nextInt();
System.out.println( location(i) );
}
}

}

import java.util.Scanner;

public class Main {

static final int LENGHT = 5;
int t;
int i;
int a1[] = new int[LENGHT + 1];
int a2[] = new int[LENGHT + 1];
int b1[] = new int[LENGHT];
int flg[] = new int[LENGHT + 1];
int pos;
int temp;
int local;
int local2;
int res;

public Main() {
a1[0] = 0;
a2[0] = 0;
b1[0] = 0;
a1[1] = 1;
flg[0] = 9;
for (int i = 1; i < LENGHT + 1; i++) {
a1[i] = a2[i - 1] + (i);
a2[i] = a1[i] + (flg[i - 1] - 1) * (i);
if (i < LENGHT) {
b1[i] = b1[i - 1] + (a1[i] + a2[i]) * flg[i - 1] / 2;
}
flg[i] = flg[i - 1] * 10;

}
Scanner scan = new Scanner(System.in);
t = scan.nextInt();
for (int times = 0; times < t; times++) {
i = scan.nextInt();
pos = LENGHT;
for (int j = 1; j < LENGHT; j++) {
if (i <= b1[j]) {
pos = j;
break;
}
}
temp = i - b1[pos - 1];
for (int j = 0; j < flg[pos - 1]; j++) {
if (temp <= a1[pos] + pos * j) {
local = j;
break;
} else {
temp = temp - (a1[pos] + pos * j);
}
}
local = (int) Math.pow(10, pos - 1) + local;
for (int i = 1; i < LENGHT + 1; i++) {
if (temp <= flg[i - 1] * i) {
local2 = i;
break;
} else {
temp = temp - flg[i - 1] * i;
}
}
res = (int) Math.pow(10, local2 - 1);
for (; temp > local2;) {
temp -= local2;
res++;
}
String str = String.valueOf(res);
System.out.println(str.charAt(temp - 1));
}
}

public static void main(String[] args) {
new Main();
}
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。