PPractick

The problem

A ticketing system issues every ticket ID twice, once at check-in and once at check-out, except for one ticket whose holder never left. Given the full log of IDs, find the missing check-out: the one value that appears exactly once while every other value appears exactly twice. A hash map works but needs O(n) memory. XOR does it in one pass with O(1) memory, because x ^ x = 0 and the order of XORs doesn't matter, so all the pairs cancel out.

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

Function signature

int singleNumber(const vector<int>& nums);

Test cases

Input	Output	Explanation
[2, 2, 1]	1
[4, 1, 2, 1, 2]	4	The pairs don't have to be adjacent
[1]	1
[-3, 7, 7]	-3	Negative numbers work too
[0, 5, 5]	0	The single value can be 0

(Confirm: exactly one element appears once and every other element appears exactly twice; linear time and constant extra space are expected.)

How interviewers phrase it

• "Every element appears twice except for one. Find that single one, in linear time and constant extra space" (LeetCode 136).

Clarifying questions to ask

1. Exactly twice for all others? (Yes; other variants use three times.)
2. Is constant space required? (Yes, which rules out a hash map.)
3. Can values be negative? (Yes; XOR works on the bit pattern.)

Follow-ups to expect

1. "Why does XOR work?"
2. "Other approaches?"
3. "What if every other element appears three times?"
4. "What if there are two single numbers?"
5. "Complexity?"

Related questions

• Find the number that appears once, and other numbers twice 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