Block sequence in Java

1

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

1
2
3

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.

 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

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

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

 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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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