---
title: Single Number
difficulty: Easy
category: Hash Table
leetcode_id: 136
revision_count: 1
last_revision: 2026-09-12
---

# Single Number

> **LeetCode:** [#136](https://leetcode.com/problems/single-number/)
> **Сложность:** Easy
> **Категория:** Hash Table / Bit Manipulation

## Условие

Дан непустой массив целых чисел `nums`, в котором каждый элемент встречается дважды, кроме одного. Найти элемент, который встречается один раз. Решение должно быть линейным по времени и константным по памяти.

```
Input:  nums = [2,2,1]          →  Output: 1
Input:  nums = [4,1,2,1,2]     →  Output: 4
Input:  nums = [1]              →  Output: 1
```

## Ключевая идея

XOR всего массива: `a XOR a = 0`, XOR коммутативен. Парные элементы уничтожают друг друга, остаётся искомое уникальное число.

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

- **Время:** O(n) — один проход по массиву
- **Память:** O(1) — одна целочисленная переменная

## Решение (Ruby) — явный цикл

```ruby
# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)
  result = 0
  nums.each do |n|
    result = result ^ n
  end
  result
end
```

**Зачем так, а не `reduce(:^)`?**

`nums.reduce(:^)` — это магическая строчка. Кто прочитает — должен сам догадаться, что `^` это XOR, и что он делает с числами. А явный `each` + `result = result ^ n` не оставляет вопросов:

- видно, что аккумулятор `result` начинается с `0`
- видно, как каждый элемент применяется к нему
- можно добавить `puts` и посмотреть, как меняется `result` на каждом шаге (отладка)

На собеседовании `reduce(:^)` может сойти за «ниндзя-стиль», но явный цикл понятнее и надёжнее, особенно если интервьюер сам не уверен в сокращениях Ruby.

## Разбор на примере

```
nums = [4, 1, 2, 1, 2]

result = 0

Шаг 1: result = 0 XOR 4 = 4   (100)
Шаг 2: result = 4 XOR 1 = 5   (101)
Шаг 3: result = 5 XOR 2 = 7   (111)
Шаг 4: result = 7 XOR 1 = 6   (110)
Шаг 5: result = 6 XOR 2 = 4   (100)

Result: 4
```

Парные 1 и 2 взаимно уничтожились: `1 XOR 1 = 0`, `2 XOR 2 = 0`.

## Edge Cases

- **Один элемент**: `[5] → 5` — XOR не меняет значение.
- **Два элемента + один уникальный**: `[2, 3, 2] → 3` — работает независимо от расположения.
- **Отрицательные числа**: XOR работает на битовом уровне, Ruby корректно обрабатывает signed int.
- **Большие числа**: Ruby Integer неограничен, переполнения нет.
- **Пустой массив**: по условию `nums` не пуст (non-empty), но защитный `return 0 if nums.empty?` не помешает.

## Типичные ошибки

1. ❌ **Забыть про XOR и писать через Hash**: O(n) памяти вместо O(1). Задача явно на XOR.
2. ❌ **Использовать `+`/`-` вместо XOR**: сумма парных чисел с разными знаками не гарантирует взаимное уничтожение.
3. ❌ **Инициализировать `result = nums[0]` и начинать цикл с 1**: опечатки при доступе по индексу. `reduce(:^)` чище и безопаснее.
4. ❌ **Пытаться сортировать**: O(n log n) — хуже линейного.
5. ❌ **Путать `^` (XOR) с `**` (возведение в степень)**: Ruby-специфичная опечатка.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (для каждого проверить остальных) | O(n²) | O(1) | Квадратичный — сразу мимо |
| Hash Map / Set | O(n) | O(n) | Складываем/вычитаем из сета — не подходит по памяти |
| Sorting + pairwise check | O(n log n) | O(log n) / O(1) | Сортируем, идём парами — хуже линейного |
| **XOR (bit manipulation)** | **O(n)** | **O(1)** | **финальное решение** — битовая магия |

XOR — единственное константное по памяти решение. Все остальные нарушают требование O(1) memory или линейные по времени.

## Заметки после повторения

_— Заполняется после каждой тренировки._