Проверка палиндрома (число)

Проверка палиндрома (число)

Палиндром — число, которое читается одинаково слева направо и справа налево (без учёта знака).

Примеры

• 121 → палиндром (1-2-1 = 1-2-1)
• 12321 → палиндром (1-2-3-2-1 = 1-2-3-2-1)
• 123 → не палиндром (1-2-3 ≠ 3-2-1)
• -121 → не палиндром (минус не симметричен)
• 0 → палиндром
• 1 → палиндром

Решение 1: Через строку (простое)

Преобразуем число в строку и проверяем, равна ли она своей инверсии:

def is_palindrome(num: int) -> bool:
    """
    Проверяет, является ли число палиндромом.
    
    Отрицательные числа — не палиндромы (минус не симметричен).
    """
    # Отрицательные числа не палиндромы
    if num < 0:
        return False
    
    # Преобразуем в строку
    s = str(num)
    
    # Сравниваем со своей инверсией
    return s == s[::-1]

# Тестирование
test_cases = [
    (121, True),
    (12321, True),
    (123, False),
    (-121, False),
    (0, True),
    (1, True),
    (10, False),
    (1001, True),
    (9009, True),
    (999, True),
]

for num, expected in test_cases:
    result = is_palindrome(num)
    status = "✓" if result == expected else "✗"
    print(f"{status} is_palindrome({num}) = {result}")

Сложность:

• Время: O(log n), где n — число цифр
• Память: O(log n) для хранения строки

Решение 2: Математическое (без строк)

Реверсируем число и сравниваем с исходным:

def is_palindrome(num: int) -> bool:
    """
    Проверяет палиндром без преобразования в строку.
    """
    # Отрицательные числа не палиндромы
    if num < 0:
        return False
    
    original = num
    reversed_num = 0
    
    # Реверсируем число
    while num > 0:
        digit = num % 10  # Берём последнюю цифру
        reversed_num = reversed_num * 10 + digit  # Добавляем в новое число
        num = num // 10  # Удаляем последнюю цифру
    
    # Сравниваем исходное с реверсированным
    return original == reversed_num

# Тестирование
for num, expected in test_cases:
    result = is_palindrome(num)
    status = "✓" if result == expected else "✗"
    print(f"{status} is_palindrome({num}) = {result}")

Пример работы для 121:

Шаг 1: num=121, reversed=0
  digit = 121 % 10 = 1
  reversed = 0 * 10 + 1 = 1
  num = 121 // 10 = 12

Шаг 2: num=12, reversed=1
  digit = 12 % 10 = 2
  reversed = 1 * 10 + 2 = 12
  num = 12 // 10 = 1

Шаг 3: num=1, reversed=12
  digit = 1 % 10 = 1
  reversed = 12 * 10 + 1 = 121
  num = 1 // 10 = 0

Всё! 121 == 121 → True

Сложность:

• Время: O(log n)
• Память: O(1) — без дополнительной памяти

Решение 3: Оптимизированное (сравнение половин)

Сравниваем только первую половину цифр со второй:

def is_palindrome(num: int) -> bool:
    """
    Оптимизированное решение через сравнение половин.
    """
    # Отрицательные числа не палиндромы
    if num < 0:
        return False
    
    # Числа, заканчивающиеся на 0 (кроме самого 0), не палиндромы
    if num % 10 == 0 and num != 0:
        return False
    
    reversed_half = 0
    
    # Реверсируем вторую половину числа
    while num > reversed_half:
        digit = num % 10
        reversed_half = reversed_half * 10 + digit
        num = num // 10
    
    # Для чётного количества цифр: num == reversed_half
    # Для нечётного количества цифр: num == reversed_half // 10
    return num == reversed_half or num == reversed_half // 10

# Тестирование
for num, expected in test_cases:
    result = is_palindrome(num)
    status = "✓" if result == expected else "✗"
    print(f"{status} is_palindrome({num}) = {result}")

Пример работы для 12321:

Шаг 1: num=12321, reversed_half=0
  digit = 1, reversed_half = 1, num = 1232

Шаг 2: num=1232, reversed_half=1
  digit = 2, reversed_half = 12, num = 123

Шаг 3: num=123, reversed_half=12
  digit = 3, reversed_half = 123, num = 12

Всё! num=12, reversed_half=123
  Нечётное количество цифр: 12 == 123 // 10 = 12 → True

Сложность:

• Время: O(log n)
• Память: O(1)

Сравнение решений

import timeit

# Функции (определены выше)

# Тест производительности
number = 1234567890987654321
iterations = 100000

# Решение 1 (строка)
time1 = timeit.timeit(
    lambda: is_palindrome_string(number),
    number=iterations
)

# Решение 2 (математическое)
time2 = timeit.timeit(
    lambda: is_palindrome_math(number),
    number=iterations
)

# Решение 3 (половины)
time3 = timeit.timeit(
    lambda: is_palindrome_optimized(number),
    number=iterations
)

print(f"Строка: {time1:.4f}s")
print(f"Математическое: {time2:.4f}s")
print(f"Оптимизированное: {time3:.4f}s")

Граничные случаи

def test_edge_cases():
    assert is_palindrome(0) == True  # Ноль
    assert is_palindrome(1) == True  # Одна цифра
    assert is_palindrome(9) == True  # Одна цифра
    assert is_palindrome(10) == False  # Заканчивается на 0
    assert is_palindrome(100) == False  # Множество нулей
    assert is_palindrome(-123) == False  # Отрицательное
    assert is_palindrome(99) == True  # Две цифры
    assert is_palindrome(1221) == True  # Чётное количество
    assert is_palindrome(12321) == True  # Нечётное количество
    assert is_palindrome(9999999) == True  # Большое число
    assert is_palindrome(2**31 - 1) == False  # Максимум для 32-бит
    print("Все тесты пройдены!")

test_edge_cases()

Рекомендация

Для интервью используйте:

• Решение 1 (строка) — самое простое, быстро объяснить
• Решение 2 (математическое) — лучше для микро-оптимизации
• Решение 3 (половины) — самое эффективное по памяти

Основной выбор зависит от требований:

• Простота кода → решение 1
• Без доп. памяти → решение 2 или 3
• Оптимальная скорость → решение 3