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: MEDIUM_HARD
Tags: Fundamentals

Mathematics

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

def find_sum(a, d, n):
	return int(Decimal(n / 2) * Decimal(2 * a + (n - 1) * d))

def term(a, d, n):
	return a + d * (n - 1)

def solve_quadratic(a, b, c):
	return floor((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a))

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))
			q = passed + find_sum(start, i, p)
			return int(extract(n - q))
		start = term(start, i, k) + (i + 1)
		passed += sum_
solve(int(1e+100))


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
		elif nextTriangle >= n:
			return triangle
		else:
			l = mid
	return l * prefix + l * (d + l * d) // 2
ns = [1, 2, 3, 100, 2100, 31000, 999999999999999999, 1000000000000000000, 999999999999999993]

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

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
		elif 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])