Reverse the Digits

Q: Как обратить порядок цифр числа, не преобразуя его в строку?

Повторяй два шага, пока число не станет равным 0 : возьми последнюю цифру с помощью n % 10 и добавь её к результату с помощью result = result * 10 + digit , затем убери её с помощью n = n / 10 , используя целочисленное деление. Для 1234 результат растёт так: 4, 43, 432 и 4321.

НовичокМатематика и моделирование

+10

Дано неотрицательное целое число n. Верните число, полученное записью его десятичных цифр в обратном порядке. Нули, оказавшиеся в начале, пропускаются, поэтому 120 превращается в 21.

Функция

reverseDigits(n: integer) → integer

ninteger: неотрицательное целое число, которое нужно перевернуть
Возвращаетinteger: цифры числа n в обратном порядке, как число

Ограничения

0 ≤ n < 10⁹
Перевёрнутое число также помещается в знаковое 32-битное целое число.

Примеры

Ввод: n = 1234
Вывод: 4321
Пояснение: Цифры числа 1234 — это 1, 2, 3 и 4. Если читать с конца, получим 4, 3, 2 и 1, то есть 4321.

Ввод: n = 120
Вывод: 21
Пояснение: Если прочитать число в обратном порядке, в 120 цифры идут в порядке 0, 2 и 1. Начальный ноль в числе не учитывается, поэтому ответ — 21.

Ввод: n = 0
Вывод: 0
Пояснение: 0 состоит из одной цифры, и при обращении получается снова 0.

+13 скрытых тестов при отправке

Дополнительный вопрос

Если n может быть любым 32-битным целым числом, его перевёрнутое значение может не поместиться. Как обнаружить это до переполнения при умножении?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Развернуть десятичную запись — это одна строка кода на большинстве языков, и это вполне хороший первый ответ. Обычно интервьюеры задают дополнительный вопрос: как получить тот же результат без строк. Арифметическое решение основано на двух операциях: n % 10 считывает последнюю цифру, а n / 10 (целочисленное деление) удаляет её.

Разверните десятичное число

Идея

Цифры числа — это ровно символы его десятичной записи. Преобразуй n в текст, переверни символы и прочитай текст обратно как число. 1234 становится "1234", затем "4321", затем 4321.

Ведущие нули обрабатываются сами собой. При переворачивании 120 получается текст "021", а при разборе его как числа ноль в начале игнорируется, и возвращается 21.

Число меньше 10^9 содержит не более 9 цифр, а объём работы и дополнительный текст растут вместе с количеством цифр, то есть это O(log n).

Алгоритм

Преобразуй n в его десятичное представление в виде текста.
Разверни символы в обратном порядке.
Разбери текст в обратном порядке как целое число и верни его.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Извлекайте и добавляйте цифры с помощью арифметики

Идея

По одной снимай цифры с конца n и добавляй каждую в конец нового числа. n % 10 — последняя цифра n, а n / 10 с целочисленным делением убирает её. Чтобы добавить цифру d в конец result, сдвинь то, что уже есть, на один разряд влево и поставь d на место единиц: result * 10 + d.

Для 1234 значение result проходит через 4, 43, 432, 4321, а значение n — через 123, 12, 1, 0. Цикл останавливается, когда n достигает 0, поэтому он выполняется один раз для каждой цифры.

Ведущие нули никогда не появляются. Для 120 первой извлекается цифра 0, и 0 * 10 + 0 по-прежнему равно 0, поэтому она не оставляет следа. При n = 0 цикл не выполняется, и ответ — 0. Хранятся только два целых числа, поэтому дополнительная память составляет O(1).

Алгоритм

Установите result = 0.
Пока n больше 0, вычислите последнюю цифру n % 10.
Установите result = result * 10 + digit.
Удалите цифру с помощью n = n / 10, используя целочисленное деление.
Верните result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

Ловушки и крайние случаи

Большинство ошибок возникает из-за деления и условия завершения цикла.

Использование обычного деления там, где нужно целочисленное деление. В JavaScript, Python 3 и Lua n / 10 даёт 123.4, поэтому n снова не становится целым числом, а result заполняется дробными числами. Используйте Math.floor, // или целочисленное деление, предусмотренное вашим языком.
Запись цикла в виде while n >= 10. Он останавливается до обработки последней цифры, поэтому вместо 1234 получается 432.
Возврат перевёрнутого текста без преобразования его в число. "021" — это не число 21, и проверка на соответствие ожидаемому ответу не проходит.
Форматирование числа с плавающей точкой в R с помощью as.character. Когда n хранится как число с плавающей точкой, оно выводится как 1e+08 вместо 100000000, а перевёрнутый текст получается таким: 80+e1. Используйте format(n, scientific = FALSE).

Частые вопросы4

Как обратить порядок цифр числа, не преобразуя его в строку?

Повторяй два шага, пока число не станет равным 0: возьми последнюю цифру с помощью n % 10 и добавь её к результату с помощью result = result * 10 + digit, затем убери её с помощью n = n / 10, используя целочисленное деление. Для 1234 результат растёт так: 4, 43, 432 и 4321.

Что происходит с конечными нулями при обращении числа?

Они стали бы ведущими нулями, которых у числа нет, поэтому они исчезают. При обращении 120 получается 21, а при обращении 100000000 получается 1. Арифметический цикл пропускает их сам, потому что прибавление 0 к пустому результату оставляет его равным 0.

Какова временная сложность обращения порядка цифр целого числа?

Цикл выполняется один раз для каждой десятичной цифры, а число n содержит примерно log10(n) + 1 цифр, поэтому временная сложность составляет O(log n). В арифметическом варианте используется дополнительная память объёмом O(1); строковый вариант хранит цифры в виде текста, что требует O(log n) памяти.

Может ли обращение порядка цифр целого числа привести к переполнению?

Да, если входные данные могут быть любым 32-битным целым числом. 1000000009 помещается, но его обратная запись 9000000001 — нет. Здесь n меньше 10^9, поэтому обратная запись содержит не более 9 цифр и всегда помещается. Для больших входных данных перед каждым умножением проверяй result > (INT_MAX - digit) / 10.

Python

def reverseDigits(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

n = 1234

Ожидается