219. Find the Two Non-Repeating Elements in an Array

Given an array where every element appears exactly twice except for two elements that each appear exactly once, find those two elements. Print them in ascending order, space-separated.

Input: Two lines: the first contains n, the second contains n space-separated integers where every value appears exactly twice except two. Output: Print the two non-repeating elements on one line, space-separated, in ascending order.

1 <= n <= 10^5

Any set bit in the combined XOR works for the split - it doesn't have to be the lowest one, though isolating the lowest set bit (via x & (-x) or x & (~x + 1)) is the most common, reliable way to pick one deterministically.

Almost every number in the array appears exactly twice, except for TWO special numbers that each appear only once. Find those two numbers. Brute force: Use a hash map to count occurrences of each value, then collect the two values with count 1 - correct and straightforward, though it uses O(n) extra space for the hash map rather than the O(1)-space bit-manipulation approach. Optimised: XOR-ing the WHOLE array cancels every properly-paired number, leaving the XOR of just the two unique numbers - since those two numbers must differ in at least one bit (otherwise they'd be equal), any set bit in that combined result can be used to correctly SEPARATE the array into two groups, each containing exactly one of the two unique numbers (plus fully-cancelling pairs), letting a second round of XOR-ing isolate each one individually.

XOR every element of the array together; since duplicates cancel out (x XOR x = 0), the result is exactly the XOR of the two unique numbers. Pick any bit that is set in this XOR result (a bit where the two unique numbers differ), and use it to split the entire array into two groups - one where that bit is set, one where it isn't. Every duplicate pair lands in the same group (since duplicates are identical and share that bit), so XOR-ing each group separately isolates exactly one of the two unique numbers per group, all without any extra hashmap storage. Time: O(n) Space: O(1)

Build a hashmap counting the occurrences of every element in one pass over the array, then scan the map (or the array again) to pick out the two keys whose count is exactly 1. This replaces the nested scanning with O(1) average-time hashmap lookups and updates, cutting the total time to linear at the cost of extra space to store the counts. Time: O(n) Space: O(n)

For every element in the array, count how many times it occurs by scanning the rest of the array, and collect the elements whose count is exactly 1. This directly implements the problem definition using nested comparisons but repeats work since each pair of equal elements gets compared to each other from both directions. Time: O(n^2) Space: O(1)

1. XOR every single element in the array together - since XOR-ing a number with itself cancels to 0, every properly-paired number vanishes, leaving only the XOR of the two unique numbers combined. 2. Find any ONE bit position where that combined XOR result has a 1 - this means the two unique numbers DIFFER at that specific bit position. 3. Split all the numbers in the array into two groups based on whether they have that specific bit set or not. 4. XOR each group separately - since the pairs (which always match on every bit) still cancel out WITHIN their group, each group's final XOR result isolates exactly one of the two unique numbers.

Time: Two full passes through the array (one to get the combined XOR, one to split and XOR each group) - O(n) overall. Space: O(1) - only a few running XOR accumulator variables, no matter how large the array is.

Test n = 2 (the minimum, both elements are the unique pair) and n = 10^5 (upper bound), and confirm output ordering when the smaller unique value appears after the larger one in the array.

This is the natural 'level up' from the classic single-non-repeating-element XOR trick - be ready to explain the extra step (finding a differentiating bit to split into two groups) that this two-element version specifically requires.