Найти единственное число

Решение

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

Все числа в массиве встречаются ровно два раза, кроме одного числа, которое встречается один раз. Нужно найти это единственное число.

Оптимальный подход: XOR

Используем свойство XOR:

• a ^ a = 0 (число XOR с самим собой дает 0)
• a ^ 0 = a (число XOR с 0 дает само число)
• XOR коммутативна: a ^ b ^ c = a ^ c ^ b

Проходим по массиву и XOR-им все числа. Парные числа дадут 0, а единственное число останется.

Реализация

def single_number_xor(nums: list[int]) -> int:
    """Найти единственное число, используя XOR"""
    result = 0
    for num in nums:
        result ^= num
    return result


def single_number_hash(nums: list[int]) -> int:
    """Найти единственное число, используя хеш-таблицу"""
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    
    for num, cnt in count.items():
        if cnt == 1:
            return num
    
    return 0


def single_number_math(nums: list[int]) -> int:
    """Найти единственное число, используя математику"""
    return 2 * sum(set(nums)) - sum(nums)

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

import pytest

class TestSingleNumber:
    """Набор тестов для поиска единственного числа"""
    
    @pytest.mark.parametrize("nums,expected", [
        ([2, 2, 1], 1),
        ([4, 1, 2, 1, 2], 4),
        ([0], 0),
        ([1, 1, 2], 2),
        ([99, 99, 100], 100),
        ([-1, -1, 0, 0, 5], 5),
        ([1, 2, 3, 2, 3, 1, 4], 4),
    ])
    def test_single_number_xor(self, nums, expected):
        """Тест метода XOR"""
        assert single_number_xor(nums) == expected
    
    @pytest.mark.parametrize("nums,expected", [
        ([2, 2, 1], 1),
        ([4, 1, 2, 1, 2], 4),
        ([1, 1, 2], 2),
    ])
    def test_single_number_hash(self, nums, expected):
        """Тест метода хеш-таблицы"""
        assert single_number_hash(nums) == expected
    
    @pytest.mark.parametrize("nums,expected", [
        ([2, 2, 1], 1),
        ([4, 1, 2, 1, 2], 4),
        ([1, 1, 2], 2),
    ])
    def test_single_number_math(self, nums, expected):
        """Тест математического метода"""
        assert single_number_math(nums) == expected
    
    def test_single_element(self):
        """Один элемент в массиве"""
        nums = [42]
        assert single_number_xor(nums) == 42
        assert single_number_hash(nums) == 42
    
    def test_negative_numbers(self):
        """Отрицательные числа"""
        nums = [-1, -1, -2, -2, 5]
        assert single_number_xor(nums) == 5
        assert single_number_hash(nums) == 5
    
    def test_zero_as_unique(self):
        """Ноль как единственное число"""
        nums = [0, 5, 5]
        assert single_number_xor(nums) == 0
        assert single_number_hash(nums) == 0
    
    def test_large_numbers(self):
        """Большие числа"""
        nums = [1000000, 1000000, 999999]
        assert single_number_xor(nums) == 999999
    
    def test_mixed_large_and_small(self):
        """Смешанные большие и маленькие числа"""
        nums = [1, 1, 1000000, 1000000, 2]
        assert single_number_xor(nums) == 2
    
    def test_all_same_pair_except_one(self):
        """Все пары одинаковые кроме последнего"""
        nums = [7, 7, 8, 8, 9, 9, 10]
        assert single_number_xor(nums) == 10

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

XOR (оптимальный)

• Время: O(n)
• Память: O(1)
• Плюсы: самый эффективный, без дополнительной памяти

Хеш-таблица

• Время: O(n)
• Память: O(n)
• Плюсы: интуитивный, работает для разного количества повторений

Математика

• Время: O(n)
• Память: O(n)
• Плюсы: интересный и компактный подход

Ключевые аспекты QA

• Граничные случаи: один элемент, отрицательные числа, ноль
• Большие массивы и большие значения чисел
• Все три метода дают одинаковый результат