Разворот числа: как избежать переполнения без 64-бит

Вы когда-нибудь решали задачу на LeetCode, чувствовали удовлетворение, закрывали вкладку, а на следующий день понимали, что упустили что-то важное? Именно так случилось с задачей Reverse Integer. И разница между первым и вторым решением — не в числах, а в подходе: анализировать всё заранее или проверять каждый шаг по мере движения. Разберём оба варианта и выясним, какой из них стоит применять в реальных проектах.

Суть задачи

Дано 32-битное целое число x. Нужно развернуть его цифры. Если результат выходит за пределы диапазона [-2^31, 2^31 - 1], вернуть 0. Главное ограничение: нельзя использовать 64-битные типы для проверки переполнения — нужно мыслить в рамках 32-битной арифметики.

Перевернуть цифры тривиально. Сложность в том, чтобы корректно обработать границы диапазона. Именно это ограничение превращает простую задачку в проверку вашего инженерного мышления.

Первый подход: анализ границ до начала работы

Моя первая мысль была: изучить максимальное значение 2147483647 и понять, когда развёрнутое число может его превысить. Я заметил, что последняя цифра исходного числа становится первой цифрой результата. Если она меньше 2 — всё безопасно. Если равна 2 — нужно сравнить остаток с 147483647. Если больше 2 — переполнение гарантировано, если только в числе не меньше 10 цифр.

Этот подход — классический анализ граничных случаев. Он корректен, но требует предварительного анализа и нескольких вспомогательных функций. Вот как это выглядело:

class Solution:
    def reverse_number(self, number):
        is_negative = number < 0
        number = abs(number)
        reversed_number = 0
        while number != 0:
            last_digit = number % 10
            number //= 10
            reversed_number = reversed_number * 10 + last_digit
        return -reversed_number if is_negative else reversed_number

    def get_last_digit(self, number):
        return abs(number - int(number / 10) * 10)

    def get_number_without_last_digit(self, number):
        return int(number / 10)

    def count_digits(self, number):
        number = abs(number)
        if number == 0:
            return 1
        digit_count = 0
        while number != 0:
            number //= 10
            digit_count += 1
        return digit_count

    def is_remaining_number_in_limit(self, number):
        if number < 0:
            return abs(number) <= 147483648
        return number <= 147483647

    def reverse(self, x: int) -> int:
        first_digit_after_reversal = self.get_last_digit(x)
        remaining_number = self.get_number_without_last_digit(x)

        if first_digit_after_reversal < 2:
            return self.reverse_number(x)

        if first_digit_after_reversal == 2:
            remaining_reversed_number = self.reverse_number(remaining_number)
            if not self.is_remaining_number_in_limit(remaining_reversed_number):
                return 0
            return self.reverse_number(x)

        remaining_digit_count = self.count_digits(remaining_number)
        if remaining_digit_count < 9:
            return self.reverse_number(x)
        return 0

Код работает, но в нём чувствуется избыточность. Мы выполняем предварительный анализ, а затем всё равно проходим по цифрам для разворота. Нельзя ли совместить эти шаги?

Второй подход: инкрементальная проверка инварианта

Ключевая идея: вместо того чтобы анализировать всю операцию заранее, мы можем проверять каждый шаг на лету. В процессе разворота мы строим число по цифрам. На каждом шаге мы можем спросить: «Не выйдет ли текущее частичное число за границы, если я добавлю следующую цифру?» Если выйдет — сразу возвращаем 0.

Инвариант: частичное развёрнутое число всегда остаётся в допустимом 32-битном диапазоне. Мы никогда не позволяем невалидному значению даже временно существовать.

Как это работает: если текущее число больше 214748364, то добавление любой цифры вызовет переполнение. Если равно 214748364, то переполнение произойдёт только при добавлении цифры больше 7. Для отрицательных чисел зеркально: меньше -214748364 — переполнение, равно -214748364 — опасно при цифре меньше -8.

Вот код:

class Solution:
    def make_room_for_new_digit(self, number):
        return number * 10

    def append_digit(self, number, digit):
        return self.make_room_for_new_digit(number) + digit

    def get_last_digit(self, number):
        return number - int(number / 10) * 10

    def is_negative(self, number):
        return number < 0

    def would_appending_digit_overflow(self, number, digit):
        if self.is_negative(number):
            return (
                number < -214748364
                or (number == -214748364 and digit < -8)
            )
        return (
            number > 214748364
            or (number == 214748364 and digit > 7)
        )

    def remove_last_digit(self, number):
        return int(number / 10)

    def reverse(self, x: int) -> int:
        reversed_number = 0
        remaining_number = x

        while remaining_number != 0:
            next_digit = self.get_last_digit(remaining_number)

            if self.would_appending_digit_overflow(reversed_number, next_digit):
                return 0

            reversed_number = self.append_digit(reversed_number, next_digit)
            remaining_number = self.remove_last_digit(remaining_number)

        return reversed_number

Этот код проще: один цикл, одна проверка, и никаких вспомогательных функций для подсчёта цифр или анализа остатка. Логика переполнения сжата в одно условие, которое выполняется на каждой итерации.

Сравнение подходов

Оба решения корректны и проходят все тесты. Но они отражают разные способы мышления. Первый — «сначала спланируй, потом действуй». Второй — «действуй, но проверяй каждый шаг». Второй подход более универсален и легче масштабируется на другие задачи.

Паттерн: инкрементальное построение с проверкой инварианта

Этот паттерн встречается в программировании повсеместно:

Парсинг и валидация: вместо проверки всей строки на корректность, отслеживайте состояние (например, глубину скобок) и отклоняйте данные сразу при нарушении.
Потоковая обработка: когда входные данные приходят частями, невозможно увидеть всё сразу — проверяйте каждый чанк на лету.
Бюджетные ограничения: добавляйте элементы по одному и останавливайтесь, как только сумма превысит лимит.
Построение структур данных с ограничениями: вставка в сбалансированное дерево или ограниченную очередь всегда сопровождается проверкой инварианта.

Суть в том, чтобы не анализировать весь вход заранее, а строить результат пошагово, задавая на каждом шаге локальный вопрос: «Не нарушит ли следующий шаг моё ограничение?» Это проще, чем пытаться предсказать будущее.

Практический вывод

Прямо сейчас откройте LeetCode, найдите задачу Reverse Integer и решите её вторым способом. Затем перечитайте свой старый код — и вы увидите, как часто вы усложняете, когда можно проверить инвариант на лету. В следующих задачах на массивы или строки попробуйте сначала подумать: можно ли проверять ограничение по мере построения результата? Этот навык сэкономит вам часы на собеседованиях и в реальной работе.

Разворот числа: как избежать переполнения без 64-бит