Обработка большого числа

Question

У меня есть эта проблема:

Положительное целое число называется palindrome, если его представление в десятичной системе одинаково при чтении слева направо и справа налево. Для заданного положительного целого числа K, состоящего не более чем из 1000000 цифр, запишите для вывода значение наименьшего палиндрома, большее K. Числа всегда отображаются без начальных нулей. Ввод

Первая строка содержит целое число t, количество тестовых случаев. Целые числа K приведены в следующих строках t. Выход

Для каждого K выведите наименьший палиндром, больший, чем K. Пример

Введите:

2
808
2133

Выход:

818
2222

Мой код преобразует входные данные в строку и оценивает любой конец строки, соответственно внося коррективы и перемещаясь внутрь. Однако проблема требует, чтобы он мог принимать значения длиной до 10 ^ 6 цифр, если я пытаюсь проанализировать большие числа, я получаю исключение формата чисел, т.е.

Integer.parseInt(LARGENUMBER);

или

Long.parseInt(LARGENUMBER);

и LARGENUMBER вне диапазона. Кто-нибудь может придумать обходной путь или как справиться с такими большими числами?

Answer 1

Подумайте о своих шагах, которые вы делаете сейчас.Вы видите что-то, что кажется немного лишним, поскольку вы конвертируете число в строку для его обработки?

Answer 2

Возможно, вы могли бы использовать класс BigInteger для обработки больших целых чисел, подобных этой.

Однако я бы не стал рассчитывать на его эффективность при таких огромных размерах. Потому что он все еще использует O(n^2) алгоритмы для умножения и преобразования.

Answer 3

Хотя эта проблема говорит о целых числах, она делает это только для ограничения ввода и вывода символов и формата.Это действительно вопрос строковых операций с тщательным отбором.Поскольку дело обстоит именно так, вам действительно не нужно читать входные данные как целые числа, а только строки.

Это сделает проверку палиндрома простой.Единственное, что вам нужно отработать, это выбрать следующий более высокий.