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;
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;
}
}
}
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));
}
}
