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 `0`.  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.
```

More examples in the test cases. Good luck!

Difficulty: interview

Starter code:

def solve(n):
	

Solutions:
def solve(n):
    def length(n):
        s = 0
        for i in range(20):
            o = 10 ** i - 1
            if o > n: break
            s += (n - o) * (n - o + 1) // 2
        return s

    def binary_search(k):
        n = 0
        for p in range(63, -1, -1):
            if length(n + 2 ** p) < k: n += 2 ** p
        return n

    def sequence(n):
        if n < 10: return n
        for i in range(1, 19):
            segment = i * 9 * 10 ** (i - 1)
            if n <= segment:
                return str(10 ** (i - 1) + (n - 1) // i)[(n - 1) % i]
            else:
                n -= segment
    return int(sequence(n - length(binary_search(n))))

from itertools import count
from math import floor
from decimal import Decimal 

#for finding sum upto nth element of arithmetic prograssion starting with a with different d
def find_sum(a, d, n):     
    return int(Decimal(n / 2) * Decimal((2 * a) + ((n - 1) * d)))

#for finding nth term of arithmetic prograssion 
def term(a, d, n):
    return a + (d * (n - 1))

#for solvinng quadratic equation
def solve_quadratic(a, b, c):
    return floor((-b + ((b ** 2) - (4 * a * c)) ** .5) / (2 * a))

#for finding nth value of seq 123456789101112.....
def extract(n):
    passed = 0
    for i in count(1):
        k = 9 * (10 ** (i - 1)) * i
        if passed + k >= n:
            return str(int(10 ** (i - 1) + (n - passed) // i))[int(n - passed) % i]
        passed += k       

def solve(n):     
    n, start, passed = n-1, 1, 0
    for i in count(1):
        k = 9 * 10 ** (i - 1)
        sum_ = find_sum(start, i, k)
    
        if passed + sum_ >= n:
            p = solve_quadratic(i, 2 * start - i, -((n - passed) * 2)) #a, b, c of quad eq
            q = passed + find_sum(start, i, p) 
            return int(extract(n - q))

        start = term(start, i, k) + (i + 1)
        passed += sum_


solve(int(1e100))

def getGreatest(n, d, prefix):
    rows = 9 * 10**(d - 1)
    triangle = rows * (d + rows * d) // 2
    l = 0
    r = triangle
    
    while l < r:
        mid = l + ((r - l) >> 1)
        triangle = mid * prefix + mid * (d + mid * d) // 2
        prevTriangle = (mid-1) * prefix + (mid-1) * (d + (mid-1) * d) // 2
        nextTriangle = (mid+1) * prefix + (mid+1) * (d + (mid+1) * d) // 2
        if triangle >= n:
            if prevTriangle < n:
                return prevTriangle
            else:
                r = mid - 1
        else:
            if nextTriangle >= n:
                return triangle
            else:
                l = mid
        
    
    return l * prefix + l * (d + l * d) // 2

ns = [
  1, # 1
  2, # 1
  3, # 2
  100, # 1
  2100, # 2
  31000, # 2
  999999999999999999, # 4
  1000000000000000000, # 1
  999999999999999993, # 7
]


def solve(n):
    debug = 1
    d = 0
    p = 0.1
    prefixes = [0]
    sections = [0]
    
    while sections[d] < n:
        d += 1
        p *= 10
        rows = int(9 * p)
        triangle = rows * (d + rows * d) // 2
        section = rows * prefixes[d-1] + triangle
        sections.append(sections[d-1] + section)
        prefixes.append(prefixes[d-1] + rows * d)
        
    section = sections[d - 1]
    n = n - section
    rows = getGreatest(n, d, prefixes[d - 1])
    
    n = n - rows
    d = 1
    while prefixes[d] < n:
        d += 1;
        
    if prefixes[d] == n:
        return 9;
    
    prefix = prefixes[d - 1]
    n -= prefix
    countDDigitNums = n // d
    remainder = n % d
    prev = 10**(d - 1) - 1
    num = prev + countDDigitNums
    
    if remainder:
        return int(str(num + 1)[remainder - 1])
    else:
        s = str(num);
        return int(s[len(s) - 1])

import math


def seq_len_formula(s, b, n, i): return s + i * b + n * (i * (i + 1) // 2)


def increasing_step(num_len, block_len, seq_len):
    num_of_blocks = 9 * 10 ** num_len
    num_len += 1
    seq_len = seq_len_formula(seq_len, block_len, num_len, num_of_blocks)
    block_len = block_len + num_len * num_of_blocks
    return num_len, block_len, seq_len


def solve(n):
    buffer = IS_seq_len = 0, 0, 0

    while IS_seq_len[2] < n:
        num_len, block_len, seq_len = buffer = IS_seq_len
        IS_seq_len = increasing_step(num_len, block_len, seq_len)

    num_len, init_block_len, init_seq_len = buffer
    step = 9 * 10 ** num_len
    num_len += 1
    buffer = (0, init_seq_len)

    while step > 0:
        num_of_blocks, seq_len = buffer
        while seq_len < n:
            buffer = num_of_blocks, seq_len
            num_of_blocks += step
            seq_len = seq_len_formula(init_seq_len, init_block_len, num_len, num_of_blocks)
        step = round(step / 10)

    n -= buffer[1]
    buffer = IS_block_len = 0, 0, 0

    while IS_block_len[1] < n:
        num_len, block_len, seq_len = buffer = IS_block_len
        IS_block_len = increasing_step(num_len, block_len, seq_len)

    num_len = 10 ** buffer[0] - 1
    block_len = buffer[1]
    amount_of_nums = math.ceil((n - block_len) / len(str(num_len + 1)))
    n = n - amount_of_nums * len(str(num_len + 1)) - block_len - 1
    num = amount_of_nums + num_len

    return int(str(num)[n])

def solve(k): 
    k -= 1
    i, d, p, n, s = 0, 1, 0, 9, 45
    while i + s <= k:
        i += s
        p += n * d
        d += 1
        n = 10 ** d - 10 ** (d - 1)
        s = n * p + n * d * (n + 1) // 2
    k -= i
    i = int((((2 * p + d) ** 2 + 8 * k * d) ** 0.5 - (2 * p + d)) / (2 * d))
    k -= i * p + i * d * (i + 1) // 2
    i, d, s = 0, 1, 9
    while i + s <= k:
        i += s
        d += 1
        n = 10 ** d - 10 ** (d - 1)
        s = n * d
    q, r = divmod(k - i, d)
    return int(str(10 ** (d - 1) + q)[r])

def cumul(n) :
    return n*(n+1)//2

# length of the line for the n index
def length (n) :
    res = cumul(n)
    length = len(str(n))
    i = 1
    while length>1 :
        res += cumul (n-(10**i -1))
        length -=1
        i+=1
    return res 


def calculindex(d) : 
    if d <= 9 :
        return d
    
    index = index_old = 9     
    i=0
    while d> index :
        index_old = index 
        i+=1
        index = index_old +  9*(i+1)*10**i        
    d-= index_old
    if d%(i+1)== 0 :
        return (str(10**(i)+d//(i+1) -1)[-1])
    else :
        return (str(10**(i)+d//(i+1))[d%(i+1)-1])
    

def solve(n):
    print(n)
    if n<=2:
        return 1
    min = 1
    max = n
    val = int(n//2)+1
    
    while length(min)< n< length(max) and max-min>1 :
        if length(val)>n :
            max,val = val,(val+min)//2
        elif length(val)< n:
            min,val = val,(max+val)//2     
        else :
            return int(str(val)[-1])    
    dist = n-length(min)
    
    return int(calculindex(dist))

import math

def seq_len_formula(s, b, n, i): return s + i * b + n * (i * (i + 1) // 2)

def point_gen():
    num_len, block_len, seq_len = 0, 0, 0
    while True:
        yield num_len, block_len, seq_len
        num_of_blocks = 9 * 10 ** num_len
        num_len += 1
        seq_len = seq_len_formula(seq_len, block_len, num_len, num_of_blocks)
        block_len = block_len + num_len * num_of_blocks
        
def linear_search(index, parameter):
    params = {'block_len': 1, 'seq_len': 2}
    required_point = 0, 0, 0
    for point in point_gen():
        if point[params[parameter]] >= index: return required_point
        required_point = point

def index_for_block(num_len, block_len, index):
    corrector = num_of_blocks = 9 * 10 ** (num_len - 1)
    seq_len = seq_len_formula(0, block_len, num_len, num_of_blocks)
    while not seq_len < index <= seq_len_formula(0, block_len, num_len, num_of_blocks + 1):
        corrector = math.ceil(corrector / 2)
        num_of_blocks = num_of_blocks - corrector if seq_len >= index else num_of_blocks + corrector
        seq_len = seq_len_formula(0, block_len, num_len, num_of_blocks)
    return index - seq_len

def solve(index):
    initial_len, initial_block_len, initial_seq_len = linear_search(index, 'seq_len')
    index = index_for_block(initial_len + 1, initial_block_len, index - initial_seq_len)
    buffer = linear_search(index, 'block_len')
    num_len, block_len = 10 ** buffer[0] - 1, buffer[1]
    amount_of_nums = math.ceil((index - block_len) / len(str(num_len + 1)))
    return int(str(amount_of_nums + num_len)[index - amount_of_nums * len(str(num_len + 1)) - block_len - 1])

from math import sqrt, ceil, log10
import numpy as np

def getGreatest(n, d, prefix):
    rows = 9 * 10**(d - 1)
    triangle = rows * (d + rows * d) // 2
    l = 0
    r = triangle
 
    while l < r:
        mid = l + ((r - l) >> 1)
        triangle = mid * prefix + mid * (d + mid * d) // 2
        prevTriangle = (mid-1) * prefix + (mid-1) * (d + (mid-1) * d) // 2
        nextTriangle = (mid+1) * prefix + (mid+1) * (d + (mid+1) * d) // 2
 
        if triangle >= n:
            if prevTriangle < n:
                return prevTriangle
            else:
                r = mid - 1
        else:
            if nextTriangle >= n:
                return triangle
            else:
                l = mid
    return l * prefix + l * (d + l * d) // 2

def findDiff(n, x):
    mult = 1
    temp=x/10
    while temp >= 1:
        temp /= 10
        mult *= 10
    d = round(log10(mult))+1
    prefixes = 0
    for z in range(1,d):
        prefixes += (9*z*10**(z-1))
    n -= calcSeq(mult-1)
    return n-getGreatest(n, d, prefixes)
        
def calcSeq(current):
    x = np.int64(current*(current+1)/2)
    mult = 10
    temp=np.int64(current)
    while temp > 0:
        temp=current
        temp -= mult-1
        mult *= 10
        if temp> 0: x += np.int64(temp*(temp+1)/2)
    return x
            
def solve(n): 
    maxN = n
    minN = 0
    x = float(0)
    delta=2
    prev = 0
    current = round(sqrt(2*n))
    prevRight = True
    while maxN-minN>1:
        x = calcSeq(current)
        delta = abs(current-prev)
        prev = current
        if x < n and prevRight:
            current += ceil((maxN-current)/2)
            prevRight = True
        elif x < n:
            minN = current
            current += ceil((maxN-current)/2)
            prevRight = True
        elif x > n and prevRight == False:
            maxN = current
            current -= round((current-minN)/2)
            prevRight = False
        elif x > n:
            current -= round((current-minN)/2)
            prevRight = False
        else: 
            maxN = current
            minN = current-1
    if calcSeq(current) < n: 
        current+=1
    prev = current-1
    
    element = findDiff(n,prev)
    nDigits, nines = 1, 9
    total = float(nDigits*nines)
    while total < element:
        nDigits += 1
        nines *= 10
        total += nDigits*nines 
    total -= nDigits*nines
    element2 = element-total
    start = 10**(nDigits-1)
    number = str(start + ceil(element2/nDigits) - 1)
    
    return int(number[(int(element2)-1)%nDigits])

from math import sqrt, ceil, log10
import numpy as np

def getGreatest(n, d, prefix):
    rows = 9 * 10**(d - 1)
    triangle = rows * (d + rows * d) // 2
    l = 0
    r = triangle
 
    while l < r:
        mid = l + ((r - l) >> 1)
        triangle = mid * prefix + mid * (d + mid * d) // 2
        prevTriangle = (mid-1) * prefix + (mid-1) * (d + (mid-1) * d) // 2
        nextTriangle = (mid+1) * prefix + (mid+1) * (d + (mid+1) * d) // 2
 
        if triangle >= n:
            if prevTriangle < n:
                return prevTriangle
            else:
                r = mid - 1
        else:
            if nextTriangle >= n:
                return triangle
            else:
                l = mid
    return l * prefix + l * (d + l * d) // 2

def findDiff(n, x):
#print("Xdiff=", x)
    mult = 1
    temp=x/10
    while temp >= 1:
        temp /= 10
        mult *= 10
  #  print("sectionMATT=", calcSeq(mult-1))
    #print("rowMATT=", calcSeq(x-(mult-1)) )
    sLen = x-(mult-1)
    d = round(log10(mult))
   # print("WOW, slen is", sLen)
    prefixes = 0
    for z in range(1,round(d)+1):
        prefixes += (9*z*10**(z-1))
    #    print('PROIFFIXES=',prefixes)
    #print('now N IS THIS ONE? WRONG YET??: NOPE!!!!', n)
    #print("PREFIXED", prefixes)
    d+=1
    #print('D',d)
   # totEX = int((d + d*(sLen)))
  #  ort = d*sLen/2*(1+sLen)
    n -= calcSeq(mult-1)
   # print('ave Len=', int(d + d*(sLen)), d, sLen )
    #print("pewpewpew, totEXSHOULDNT BE TOO BIG=",int(totEX*sLen/2), calcSeq(mult-1))
    temp = getGreatest(n, d, prefixes)
    #print("temp=", temp)
    #print("DDDD=",d)
    #print('theN=', n)
    
    #print('theN=', n)
   # n -= totC
    #n = int(n/2  + (n - totEX*sLen)/2)#int((int(totEX)*sLen)/2)
    #for _ in range(sLen+1):
    #    n -= int(d*sLen/2)
#    print('theN=', n)
    return n-temp
        
def calcSeq(current):
    x = np.int64(current*(current+1)/2)
    mult = 10
    temp=np.int64(current)
    while temp > 0:
        temp=current
        temp -= mult-1
        mult *= 10
        if temp> 0: x += np.int64(temp*(temp+1)/2)
    return x
            
def solve(n): 
  #  print([calcSeq(x) for x in [0,9,99,999]])
    
    
    maxN = n
    minN = 0
    x = float(0)
    delta=2
    prev = 0
    current = round(sqrt(2*n))
    prevRight = True
    while maxN-minN>1:
        x = calcSeq(current)
        delta = abs(current-prev)
        prev = current
        if x < n and prevRight:
            current += ceil((maxN-current)/2)
            prevRight = True
        elif x < n:
            minN = current
            current += ceil((maxN-current)/2)
            prevRight = True
        elif x > n and prevRight == False:
            maxN = current
            current -= round((current-minN)/2)
            prevRight = False
        elif x > n:
            current -= round((current-minN)/2)
            prevRight = False
        else: 
            maxN = current
            minN = current-1
    if calcSeq(current) < n: 
        current+=1
    prev = current-1
    
    element = findDiff(n,prev)
    nDigits, nines = 1, 9
    total = float(nDigits*nines)
    while total < element:
        nDigits += 1
        nines *= 10
        total += nDigits*nines 
    
    total -= nDigits*nines
    element2 = element-total
    start = 10**(nDigits-1)
    number = str(start + ceil(element2/nDigits) - 1)
    
    return int(number[(int(element2)-1)%nDigits])