PPractick

The problem

An inventory audit scans every item twice (once in, once out), except that two items were only scanned once. Find both of those IDs, in increasing order, in linear time and O(1) extra space. XOR-ing everything leaves a ^ b, which isn't either answer directly. But a ^ b isn't zero, so some bit differs between a and b. Splitting all numbers by that bit puts a and b in different groups, while each pair stays together, so XOR-ing each group gives a and b separately.

Example: [1, 2, 1, 3, 2, 5] → [3, 5].

Function signature

vector<int> singleNumber(const vector<int>& nums);  // the two unique values, ascending

Test cases

Input	Output	Explanation
[1, 2, 1, 3, 2, 5]	[3, 5]
[-1, 0]	[-1, 0]
[0, 1]	[0, 1]
[2, 1, 2, 4]	[1, 4]
[7, 7, -8, 8]	[-8, 8]	They differ in the sign bit and more

(Confirm: exactly two values appear once and all others exactly twice; the two answers are distinct; output in increasing order.)

How interviewers phrase it

• "Exactly two elements appear only once and all the others appear exactly twice. Find the two elements, in linear time and constant extra space" (LeetCode 260).

Clarifying questions to ask

1. Exactly two singles, and everything else exactly twice?
2. What order should the answer be in? (Ascending here.)
3. Can values be negative, including INT_MIN?

Follow-ups to expect

1. "What does XOR of everything give?"
2. "How do you pick the splitting bit?"
3. "Why do pairs stay together?"
4. "What if every other number appeared three times?"
5. "Complexity?"

Related questions

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