Разворот целого числа

Средняя

medium , math , integers

08 December 2023

Описание задачи #

Дано 32-битное целое число x со знаком. Напишите функцию reverse, которая принимает на вход x, а возвращает перевернутое число.

Если изменение x приводит к выходу значения за пределы диапазона 32-битных целых чисел со знаком [-2³¹, 2³¹ - 1], верните 0. Учтите, что среда исполнения функции не позволяет хранить 64-битные целые числа со знаком или без знака.

Ограничения #

Значение x находится в диапазоне от -2³¹ до 2³¹ - 1

Примеры #

Входные данные: x = 123

Ответ: 321
Входные данные: x = -123

Ответ: -321
Входные данные: x = 120

Ответ: 21
Входные данные: x = 2147483647

Ответ: 0

Перевернутое число 7463847421 выходит за пределы 32-битного диапазона.
Входные данные: x = -2147483647

Ответ: 0

Перевернутое число -7463847421 выходит за пределы 32-битного диапазона.

Решение #

Разобьем задачу на две части:

Разворот маленького числа. Для этого воспользуемся реализацией функции reverse из задачи «Число после двойного переворота»
Обработка возможного переполнения 32-битного пространства.

Переполнение 32-битного пространство #

Как было сказано в условиях задачи, число не может превышать диапазон 32-битного пространства [-2³¹, 2³¹ - 1]. Это значит, что если мы попытаемся развернуть число 2147483647, то на последней итерации мы получим 7463847412, а оно сильно выходит за допустимые границы.

Как же нам обработать переполнение?

Давайте определим, что верхняя граница 32-битного диапазона называется MAX_INT, а нижняя — MIN_INT. Теперь сформулируем несколько правил.

Для положительных чисел

Если res > MAX_INT / 10, то после умножения его на 10 и добавления к нему right мы гарантированно получим переполнение.
Если res == MAX_INT / 10 то после умножения его на 10 и добавления к нему right мы получим переполнение только если right > 7.

Для отрицательных чисел

Если res < MIN_INT / 10, то после умножения его на 10 и добавления к нему right мы гарантированно получим переполнение.
Если res == MIN_INT / 10 то после умножения его на 10 и добавления к нему right мы получим переполнение только если right < -7.

Реализация #

Обратите внимание, что в Type Script приходится дополнительно округлять числа с плавающей точкой в зависимости от знака. Также тут нет констант для минимального и максимального 32-битных чисел, поэтому их приходится определять вручную.

package main

import (
	"math"
)

func reverse(x int) int {
	left := x
	res := 0

	for left != 0 {
		right := left % 10
		left = left / 10

		if res > math.MaxInt32/10 || res == math.MaxInt32/10 && right > 7 {
			return 0
		}
		if res < math.MinInt32/10 || res == math.MinInt32/10 && right < -7 {
			return 0
		}

		res = res*10 + right
	}

	return res
}

export const reverse = (x: number): number => {
    const maxInt32 = Math.pow(2, 31) - 1;
    const minInt32 = Math.pow(2, 31) * -1;

    let left = x
    let res = 0

    while (left !== 0) {
        const right = left % 10
        left = left > 0 ? Math.floor(left / 10) : Math.ceil(left / 10)

        const max = Math.floor(maxInt32 / 10)
        const min = Math.ceil(minInt32 / 10)

        if (res > max || res == max && right > 7) {
            return 0
        }
        if (res < min || res == min && right < -7) {
            return 0
        }

        res = res * 10 + right
    }

    return res
}

Оценка сложности #

По времени

Для разворота числа нам нужно произвести k итераций, где k — количество цифр в числе, что примерно равноlog(x). Поэтому сложность равна O(log(x)).

По памяти

O(1) — дополнительная память константна.

Оригинал задачи на Leetcode

Algorithmics