How do you find the single number where every other element appears twice?

Q: How do you find the single number where every other element appears twice?

**Target Audience:** Developers preparing for coding interviews who know arrays and loops in Python; binary and XOR are explained from scratch. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You empty a laundry basket onto the bed. Every sock has a twin, except one. The slow way is to pick up a sock and search the whole pile for its partner, again and again. A faster way is to keep a list of "socks I have seen once": add a sock when it first shows up, cross it off when its twin appears, and the one name left on the list is the odd sock. That works, but th

The problem

Question presented to candidate: "You get a non-empty list of integers in which every value appears exactly twice except one, which appears once. Write a Python function that returns that single value. Can you do it in linear time and constant extra space?"

What a strong answer should cover:

The baseline answers first: nested scan O(n²), a dict/collections.Counter of counts O(n) time and O(n) space, sorting O(n log n).
XOR: a ^ a == 0 and a ^ 0 == a, and XOR is commutative and associative, so XOR-ing everything leaves the single number.
O(n) time, O(1) extra space, and why O(n) is the best possible.
Python details: ^ is XOR (power is **), functools.reduce(operator.xor, nums, 0) is the one-liner, and Python ints are unbounded so negatives behave like an infinite run of sign bits.
The follow-ups: three-times (count bits mod 3, then convert bit 31 back to a negative number in Python) and two singles (split on the lowest set bit).

Clarifying questions expected:

Is it guaranteed that every other value appears exactly twice?
Is O(n) extra memory allowed, or must it be O(1)?

Code / implementation expected: Yes — a one-pass XOR function in Python 3, optionally with the Counter version for comparison.

arrays
bit-manipulation

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers preparing for coding interviews who know arrays and loops in Python; binary and XOR are explained from scratch.
Difficulty: Easy
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You empty a laundry basket onto the bed. Every sock has a twin, except one. The slow way is to pick up a sock and search the whole pile for its partner, again and again. A faster way is to keep a list of "socks I have seen once": add a sock when it first shows up, cross

The solution is hidden so you can try first

12 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

Pythonsingle_number with XOR, plus a trace of the running value

Practice

PythonBrute force vs dict vs sort vs sum vs XOR, with work counters

Practice

PythonFollow-ups: every other value three times, and two single values

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.