Найти пропущенное число

Решение

Понимание задачи

Дан массив из n-1 элементов со значениями от 1 до n, в котором отсутствует одно число. Нужно найти пропущенное число за O(n) время и O(1) доп. памяти.

Два подхода

1. Математический (сумма)

• Ожидаемая сумма: sum(1..n) = n*(n+1)/2
• Вычтем сумму массива из ожидаемой суммы
• Результат — пропущенное число

2. Битовая операция (XOR)

• Используем свойство: a ^ a = 0, a ^ 0 = a
• XOR всех чисел от 1 до n и всех элементов массива

Реализация

def find_missing_number_sum(nums: list[int]) -> int:
    """Найти пропущенное число используя математическую формулу"""
    n = len(nums) + 1  # Реальное количество чисел
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum


def find_missing_number_xor(nums: list[int]) -> int:
    """Найти пропущенное число используя XOR"""
    result = 0
    
    # XOR всех элементов массива
    for num in nums:
        result ^= num
    
    # XOR всех чисел от 1 до n
    n = len(nums) + 1
    for i in range(1, n + 1):
        result ^= i
    
    return result

Комплексные тесты

import pytest

class TestFindMissingNumber:
    """Набор тестов для поиска пропущенного числа"""
    
    @pytest.mark.parametrize("nums,expected", [
        ([1, 2, 4, 5, 6], 3),
        ([1], 2),
        ([2], 1),
        ([1, 2, 3, 5], 4),
        ([3, 4, 5], 1),
        ([1, 3], 2),
        ([1, 2, 3, 4, 5], 6),
    ])
    def test_find_missing_sum(self, nums, expected):
        """Тест метода суммы"""
        assert find_missing_number_sum(nums) == expected
    
    @pytest.mark.parametrize("nums,expected", [
        ([1, 2, 4, 5, 6], 3),
        ([1], 2),
        ([2], 1),
        ([1, 2, 3, 5], 4),
    ])
    def test_find_missing_xor(self, nums, expected):
        """Тест метода XOR"""
        assert find_missing_number_xor(nums) == expected
    
    def test_single_element_first(self):
        """Пропущено первое число"""
        assert find_missing_number_sum([2]) == 1
        assert find_missing_number_xor([2]) == 1
    
    def test_missing_at_start(self):
        """Пропущено число в начале"""
        nums = [2, 3, 4, 5]
        assert find_missing_number_sum(nums) == 1
    
    def test_missing_at_end(self):
        """Пропущено число в конце"""
        nums = [1, 2, 3, 4]
        assert find_missing_number_sum(nums) == 5
    
    def test_missing_in_middle(self):
        """Пропущено число в середине"""
        nums = [1, 2, 3, 5, 6, 7]
        assert find_missing_number_sum(nums) == 4
    
    def test_unordered_array(self):
        """Неупорядоченный массив"""
        nums = [5, 1, 3, 2, 6]
        assert find_missing_number_sum(nums) == 4
        assert find_missing_number_xor(nums) == 4
    
    def test_large_array(self):
        """Большой массив"""
        nums = list(range(1, 10001))
        nums.remove(5000)
        assert find_missing_number_sum(nums) == 5000
        assert find_missing_number_xor(nums) == 5000

Сравнение методов

Метод сумма

• Плюсы: простой, понятный, одна строка
• Минусы: может быть переполнение при очень больших числах

Метод XOR

• Плюсы: избегает переполнения, всегда O(1) по памяти
• Минусы: менее очевидный для начинающих

Ключевые граничные случаи

• Пропущено первое число (n=1)
• Пропущено последнее число (n=k)
• Неупорядоченный массив
• Большие массивы (проверка производительности)