---
round: 3
ticket_no: 19
source_no: 7
slug: single-number
topic: Hash Table
difficulty: Easy
leetcode_id: 136
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 19 — Single Number

## Условие (как предъявлено)

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

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

Constraints: `1 <= nums.length <= 3 * 10^4`; `-3 * 10^4 <= nums[i] <= 3 * 10^4`; каждый элемент встречается дважды, кроме одного; алгоритм должен иметь линейную сложность по времени и константную по памяти.

## Ответ

> Здесь нужно сделать решение в один проход. Получается, что мы берём накопительную одну переменную, создаём числовую. И дальше с помощью побитового сравнения XOR прибавляем туда элемент. То есть там сначала 0 лежит, вот, и дальше мы туда прибавляем. Точнее, так нет, нет, там не ноль, там первый элемент мы кладем. То есть он сначала там пустой, мы первый элемент туда кладем, и дальше суммируем туда вот этим побитовым XOR, все символы, и в итоге останется тот, который непарный. Парные будут взаимоуничтожаться.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/01-must-have/02-hash-table/07-single-number.md`](../../algo-solutions/01-must-have/02-hash-table/07-single-number.md)