PPractick

The problem

A wedding caterer counts RSVP cards: every guest sent two copies (one by mail, one online) except for one guest who sent only one. Given the list of guest IDs, find the one that appears once. A hash map of counts works, but the elegant answer uses the XOR operator: XOR-ing a number with itself gives 0 and XOR is order-independent, so XOR-ing the whole list cancels every pair and leaves only the single ID, in O(n) time and O(1) space.

Example: [4, 1, 2, 1, 2] → 4.

Function signature

int singleNumber(const vector<int>& nums);  // every value appears twice except one

Test cases

Input nums	Output	Explanation
[2, 2, 1]	1
[4, 1, 2, 1, 2]	4	Pairs don't need to be adjacent
[1]	1
[-3, 7, -3]	7	Works for negative numbers too
[0, 5, 5]	0	The single value can be 0

(Confirm: exactly one value appears once and every other value appears exactly twice; O(1) extra space is expected.)

How interviewers phrase it

• "Every element appears twice except one. Find it in linear time and constant space" (LeetCode 136).
• Harder variants: "every element appears three times except one" (LeetCode 137) or "two elements appear once" (LeetCode 260).

Clarifying questions to ask

1. Does every other value appear exactly twice?
2. Is O(1) extra space required?
3. Can values be negative?

Follow-ups to expect

1. "Why does XOR work?"
2. "What are the other approaches?"
3. "What if every other element appears three times?"
4. "What if two elements appear once?"
5. "Complexity?"

Related questions

• Single Number - I Medium
• Single Number - III Medium
• Find missing number Easy
• Longest subarray with given sum K (positives) Medium
• Longest subarray with sum K Medium
• Sort an array of 0's 1's and 2's Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in