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

Что проверяют

Умеете ли вы решить задачу одной арифметикой, без перевода числа в строку, и помните ли о граничных случаях. Уточнение почти всегда одно: «а теперь без ToString() и без лишней памяти».

Как отвечать

Сначала простой вариант: ToString() и два указателя, left с начала, right с конца, сдвигаются к центру, пока left < right. По времени O(k), где k число цифр, и O(k) памяти на строку. Потом переходите к арифметике.

Разворот половины числа:

• отсечь очевидное: отрицательные числа не палиндромы из-за знака, числа с нулём на конце тоже, кроме самого 0. Без второй проверки 10 признаётся палиндромом;
• развернуть половину: пока x > reversed, выполняем reversed = reversed * 10 + x % 10 и x /= 10;
• сравнить: при чётном числе цифр x == reversed, при нечётном x == reversed / 10, средняя цифра роли не играет.

Половина решает проблему переполнения: развёрнутый int.MaxValue в int не помещается, а половина помещается всегда.

Если просят буквально сравнивать цифры с начала и конца, покажите вариант с делителем. Находим div, степень десяти с тем же числом разрядов, что у x. Первая цифра x / div, последняя x % 10. Совпали, отрезаем обе: x = (x % div) / 10 и div /= 100. Время O(k), память O(1).

Тесты стоит перечислить вслух: 0, 7, 10, 121, 1221, -121 и 1000021. Последний ловит потерю внутренних нулей.

Где спотыкаются

Разворачивают число целиком в int. В C# переполнение по умолчанию происходит молча, без исключения, если код не в контексте checked, и на больших значениях ответ получается неверным.

Отрезав крайние цифры, заново считают разряды по новому числу вместо div /= 100. У 1000021 после первого шага остаётся 2, внутренние нули теряются, и функция возвращает true.

Путают размер входа и называют сложность O(n) от самого числа. Цикл идёт по цифрам, их около log10(n), и для int это не больше десяти итераций.