Выпишите натуральные числа подряд: 123456789101112131415... На позиции 1 стоит 1, на позиции 10 стоит единица из числа 10, на позиции 11 стоит ноль из числа 10. Для каждой запрошенной позиции найдите стоящую там цифру. Позиции бывают настолько большими, что строку такой длины не построить. Пропускайте целые блоки чисел с одинаковым количеством цифр (9 однозначных чисел, 90 двузначных, 900 трёхзначных, ...).
Реализуйте champernowne_digits(positions).
Входные данные
positions: позиции в строке цифр, считая с 1.
Выходные данные
Верните цифру на каждой позиции в том же порядке, что и во входных данных. Для пустого входа верните пустой список.
Ограничения
0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15
Примеры
Ввод:
positions = [1, 9, 10, 11]
Ожидаемый вывод:
expected = [1, 9, 1, 0]
Ввод:
std::vector<long long> positions = {1, 9, 10, 11};
Ожидаемый вывод:
std::vector<long long> expected = {1, 9, 1, 0};
Ввод:
long[] positions = new long[] {1, 9, 10, 11};
Ожидаемый вывод:
long[] expected = new long[] {1, 9, 1, 0};
Пояснение
Строка начинается с 1 2 3 4 5 6 7 8 9 1 0 1 1, поэтому цифры равны [1, 9, 1, 0].
Ввод:
positions = [15, 190]
Ожидаемый вывод:
expected = [2, 1]
Ввод:
std::vector<long long> positions = {15, 190};
Ожидаемый вывод:
std::vector<long long> expected = {2, 1};
Ввод:
long[] positions = new long[] {15, 190};
Ожидаемый вывод:
long[] expected = new long[] {2, 1};
Пояснение
Позиция 15 - это двойка из числа 12. Позиции с 10 по 189 занимают числа от 10 до 99, поэтому на позиции 190 стоит первая цифра числа 100: [2, 1].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Числа из d цифр занимают в сумме 9 × 10^(d − 1) × d позиций.
Подсказка 2
Вычитайте целые блоки, пока позиция не окажется внутри одного из них.
Подсказка 3
Внутри блока (позиция − 1) / d показывает, какое это число, а (позиция − 1) % d показывает, какая это цифра.
Ожидаемая сложность
время O(m × log P) для m позиций, доп. память O(m)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.