Число после двойного переворота

Легкая

easy , math , integers

04 December 2023

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

Дано целое число num. Переверните число, чтобы получить reversed1, затем переверните reversed1, чтобы получить reversed2. Верните true, если перевернутое значение reversed2 равно исходному числу num. В противном случае верните false.

Перевернуть целое число означает, что вам необходимо перевернуть все его цифры. Например, переворот числа 2021 дает число 1202. Переворот числа 12300 дает 321, поскольку ведущие нули не сохраняются.

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

Значение num находится в диапазоне от 0 до 10⁶

Примеры #

Входные данные: num = 526

Ответ: true
Входные данные: num = 1800

Ответ: false
Входные данные: num = 0

Ответ: true

Решение #

Для начала создадим вспомогательную функцию reverse, которая будет переворачивать переданное ей число.

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

Получить последнюю цифру от числа крайне просто, так как это остаток от деления числа на десять. Получить же «левую» часть можно оставив лишь целую часть от деления числа на 10.

right = x % 10
left = x / 10

То есть мы получим следующие значения.

right = 3
left = 12

А вот из последне цифры сделать первую уже немного сложнее.

Для начала создадим переменную res, которая на старте будет равна 0 и в которой мы будем хранить итоговое число. Чтобы в нашем результате последняя цифра стала первой, достаточно к res прибавить right.

res = res + right

Таким образом после первой итерации мы имеем следующие значения.

left = 12
right = 3
res = 3

Теперь надо повторить вычисления. Выделяем новую левую часть и последнюю цифру.

left = 1
right = 2
res = 3

Теперь, если мы попробуем прибавить к res правую цифру, то получим 2 + 3 = 5, что будет неверным ответом. Нам надо сделать так, чтобы добавленная цифра занимала следующий разряд. Для этого нам сначала нужно res умножить на 10. Таким образом мы получим 30 вместо 3, а добавив к числу 2, получим 32, что уже является корректной последовательностью.

Исходя из этого правильная формула для вычисления res будет выглядеть так.

res = res * 10 + right

Проделываем итерацию еще раз и получаем итоговые значения.

left = 0
right = 1
res = 321

Как мы видим, после обработки последней цифры left всегда будет равен 0, поэтому цикл мы будем выполнять до тех пор, пока left != 0.

func reverse(num int) int {
	res := 0

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

		res = res * 10 + right
	}

	return res
}

const reverse = (num: number): number => {
    let res = 0

    while (num != 0) {
        const right = num % 10
        num = Math.floor(num / 10)
        res = res * 10 + right
    }

    return res
}

Теперь, имея готовую функцию нам достаточно перевернуть исходное число дважды и сравнить результаыт.

Реализация #

package main

func reverse(num int) int {
	res := 0

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

		res = res*10 + right
	}

	return res
}

func isSameAfterReversals(num int) bool {
	reversed1 := reverse(num)
	reversed2 := reverse(reversed1)

	return num == reversed2
}

const reverse = (num: number): number => {
    let res = 0

    while (num != 0) {
        const right = num % 10
        num = Math.floor(num / 10)
        res = res * 10 + right
    }

    return res
}

export const isSameAfterReversals = (num: number): boolean => {
    const reversed1 = reverse(num)
    const reversed2 = reverse(reversed1)

    return num == reversed2
}

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

По времени

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

По памяти

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

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

Algorithmics