# Single Element Among Pairs

> One element has no partner.

Canonical URL: <https://datadriven.io/problems/single_element_among_pairs>

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

Given a sorted list of integers where every element appears exactly twice except one that appears once, return the unique element.

## Worked solution and explanation

### Why this problem exists in real interviews

Finding the unpaired element tests **XOR bit manipulation**. XORing all elements cancels out pairs (since `x ^ x = 0`), leaving only the single element. This is the canonical O(n) time, O(1) space solution.

> **Trick to Solving**
>
> XOR all elements together. Since every paired element cancels itself (`a ^ a = 0`), only the single unpaired element remains. This works because XOR is both commutative and associative.

---

### Break down the requirements

#### Step 1: Initialize a running XOR value to 0

Zero is the identity element for XOR: `0 ^ x = x`.

#### Step 2: XOR every element into the accumulator

Pairs cancel out, leaving only the unique value.

---

### The solution

**XOR accumulation to isolate the unpaired element**

```python
def find_single(nums):
    result = 0
    for num in nums:
        result ^= num
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) with a single pass.
> 
> **Space:** O(1). One integer accumulator.

> **Interviewers Watch For**
>
> Using XOR instead of a set or Counter. The XOR approach is O(1) space, which is the optimal solution for this problem pattern.

> **Common Pitfall**
>
> Using a set to track unpaired elements. While correct, this uses O(n) space. The XOR approach is strictly better for this specific problem structure.

---

## Common follow-up questions

- What if two elements are unpaired instead of one? _(Tests XOR-based partitioning: XOR all elements, use a set bit to split into two groups, then XOR each group.)_
- What if elements appear three times except one? _(Tests bitwise counting modulo 3 across all bit positions.)_
- Why does XOR work here but not for finding a missing number? _(Tests understanding that XOR finds the symmetric difference: it works for both unpaired and missing number problems.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/single_element_among_pairs)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.