## The challenge#

Consider the following array:

``````[1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 12345678910, 1234567891011...]
``````

If we join these blocks of numbers, we come up with an infinite sequence which starts with `112123123412345123456...`. The list is infinite.

You will be given an number (`n`) and your task will be to return the element at that index in the sequence, where `1 ≤ n ≤ 10^18`. Assume the indexes start with `1`, not ``. For example:

``````solve(1) = 1, because the first character in the sequence is 1. There is no index 0.
solve(2) = 1, because the second character is also 1.
solve(3) = 2, because the third character is 2.
``````

## The solution in Java code#

Option 1:

``````class Solution{
private static long bSearch(long n) {
long res = 0, i = 1, k = 9, j = 9;
for (; j < n; ++i, k *= 10, j += k){
res += i * k * (k + 1) / 2;
res += i * k * (n - j);
}
k = n - j / 10;
res += i * k * (k + 1) / 2;
return res;
}

public static int solve(long n) {
n--;
long lb = 0, rb = (long)1e9;
while (lb < rb){
long mb = (lb + rb + 1) / 2;
if (bSearch(mb) > n) rb = mb - 1;
else lb = mb;
}
n -= bSearch(lb);
long cnt = 9, len = 1;
while (n >= cnt * len){
n -= cnt * len;
cnt *= 10;
++len;
}
String x = String.valueOf(cnt / 9 + n / len);
int y = (int)(n % len);
return x.charAt(y) - '0';
}
}
``````

Option 2:

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

Numbers(long start, long add) {
this.start = start;
}
}
}
``````

Option 3:

``````class Solution{
public static long bSearch(long n){
long res = 0, i = 1, k = 9, j = 9;
for (; j < n; ++i, k *= 10, j += k){
res += i * k * (k + 1) / 2;
res += i * k * (n - j);
}
k = n - j / 10;
res += i * k * (k + 1) / 2;
return res;
}
public static int solve(long n){
n--;
long lb = 0, rb = (long)1e9;
while (lb < rb){
long mb = (lb + rb + 1) / 2;
if (bSearch(mb) > n) rb = mb - 1;
else lb = mb;
}
n -= bSearch(lb);
long cnt = 9, len = 1;
while (n >= cnt * len){
n -= cnt * len;
cnt *= 10;
++len;
}
String x = String.valueOf(cnt / 9 + n / len);
int y = (int)(n % len);
return x.charAt(y) - '0';
}
}
``````

## Test cases to validate our solution#

``````import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest{
@Test
public void basicTests(){
assertEquals(1, Solution.solve(1L));
assertEquals(1, Solution.solve(2L));
assertEquals(2, Solution.solve(3L));
assertEquals(1, Solution.solve(100L));
assertEquals(2, Solution.solve(2100L));
assertEquals(2, Solution.solve(3100L));
assertEquals(1, Solution.solve(55L));
assertEquals(6, Solution.solve(123456L));
assertEquals(3, Solution.solve(123456789L));
assertEquals(4, Solution.solve(999999999999999999L));
assertEquals(1, Solution.solve(1000000000000000000L));
assertEquals(7, Solution.solve(999999999999999993L));
}
}
``````