Single Element Among Pairs

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Alcon

Problem

Return the event id our replicated log wrote only once. Every other id in nums was written exactly twice, and the two copies of an id can land anywhere in the log.

One element has no partner.

Example 1

Input:

nums = [4012,3870,4415,3870,4012]

Output:

4415

Example 2

Input:

nums = [518,733,902,518,902,733,641]

Output:

641

Worked solution and explanation

This is odd-occurrence detection dressed up as a replication audit. When the copies of an id sit side by side, anyone can find the lone id, and this problem quietly takes that crutch away: a replicated log writes each copy wherever its writer happens to finish. The trap is reading the tidy-looking ids as ordered and comparing neighbors. Do that on [4012, 3870, 4415, 3870, 4012] and you report '4012', an id that was replicated perfectly, while the write that actually went missing is never flagged.

Why position cannot be the signal

Step 1: Stop looking at neighbors

Any test of the form nums[i] != nums[i + 1] asks where an id sits, and here position carries no information. The question that does carry it is how many times each value occurs: every id occurs twice except one.

Step 2: Let each pair erase itself

x ^ x == 0 and 0 ^ x == x. XOR is commutative and associative, so you can fold the log in any order and every pair cancels, wherever its two copies landed. The only bits left standing belong to the id written once.

Step 3: Start the accumulator at 0

Zero is the identity for XOR, so a one-entry log like [907] needs no special case: the fold returns '907' directly. There is no pairwise indexing, so nothing can run past the end.

Fold every id into one XOR accumulator
def single_element_among_pairs(nums: list[int]) -> int:
    unpaired = 0
    for event_id in nums:
        # an id seen twice cancels itself: x ^ x == 0
        unpaired ^= event_id
    return unpaired
Neighbor scan
Steps through the log in pairs and returns the first nums[i] that differs from nums[i + 1]. It is right only when copies happen to be adjacent; on the first example it returns '4012'.
XOR fold
unpaired ^= event_id over every entry. Order never enters the computation, so it returns '4415' on the same log, and '641' when the lone id is last.

Common follow-up questions