1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
public class Solution {
public static int solve(long n) {
return getPoz(getShorterNumber(n));
}
private static long getShorterNumber(long n) {
long shortN = n;
long add = 1;
int digits = 1;
Numbers[] SAFE_TO_REMOVE = {
new Numbers(45L, 11L),
new Numbers(9045L, 192L),
new Numbers(1395495L, 2893L),
new Numbers(189414495L, 38894L),
new Numbers(23939649495L, 488895L),
new Numbers(2893942449495L, 5888896L),
new Numbers(339393974949495L, 68888897L),
new Numbers(38939394344949495L, 788888898L),
new Numbers(4393939398494949495L, 8888888899L)
};
for (int i = 0; i < SAFE_TO_REMOVE.length; i++) {
if (SAFE_TO_REMOVE[i].start >= n) {
if (i > 0) {
shortN = n - SAFE_TO_REMOVE[i - 1].start;
add = SAFE_TO_REMOVE[i - 1].add;
digits = i + 1;
}
break;
}
}
return getEvenShorterNumber(digits, add, shortN - 1);
}
public static long getEvenShorterNumber(long digit, long start, long n) {
BigDecimal b = BigDecimal.valueOf((start - 0.5 * digit));
double X = b.multiply(b)
.add(BigDecimal.valueOf(2).multiply(BigDecimal.valueOf(digit)).multiply(BigDecimal.valueOf(n)))
.sqrt(MathContext.DECIMAL64)
.subtract(b)
.divide(BigDecimal.valueOf(digit), 8, RoundingMode.HALF_UP)
.doubleValue();
long longX = (long) X;
long shorterNumber = (2L * start + (longX - 1L) * digit) * longX / 2L;
return (n - shorterNumber + 1);
}
private static int getPoz(long n) {
long n0 = n - 1;
long prevN;
int i = 0;
do {
prevN = n0;
n0 -= 9 * Math.pow(10.0, i) * (i + 1);
i++;
} while (n0 >= 0);
long number = (long) Math.pow(10.0, i - 1) + prevN / i;
int digitPoz = (int) (prevN % i);
String digit = String.valueOf(number).substring(digitPoz, digitPoz + 1);
return Integer.decode(digit);
}
private static class Numbers {
final long start;
final long add;
Numbers(long start, long add) {
this.start = start;
this.add = add;
}
}
}
|