XOR finds one number without a partner. With one more idea, it can find two.
What to build
A program that finds the two numbers that appear once, in a list where every other number appears twice.
Requirements
- Use one pass to XOR everything, and a second pass to split the numbers into two groups.
- Keep the numbers in one array, and use no sorting and no counting table.
- Print the two numbers in increasing order.
Input
The first line has n, which is even. The second line has the n numbers.
Output
The two numbers that appear once, smaller first, separated by a space.
Constraints
2 ≤ n ≤ 1000, and each number is from 0 to 1 000 000 000.
Example
Input:
6
1 2 1 3 2 5
Output:
3 5
Why it works
The two singles differ at the chosen bit, so they land in different groups. Each pair has equal bits and lands in the same group, where it cancels, so each group's XOR is exactly one of the singles.
Examples
6 1 2 1 3 2 5
3 5
2 2 1
1 2
Hints
Hint 1
XOR of everything gives `a ^ b`, where `a` and `b` are the two you want. It cannot be 0, since they differ.
Hint 2
Any set bit of that value is a place where `a` and `b` differ. `x & -x` picks the lowest one.
Hint 3
Split the numbers into two groups by that bit, and XOR each group separately. Each pair stays together in one group.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int a[1000];
int main(void) {
int n;
scanf("%d", &n);
int all = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
all ^= a[i];
}
int low = all & -all;
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (a[i] & low) x ^= a[i];
else y ^= a[i];
}
if (x < y) printf("%d %d\n", x, y);
else printf("%d %d\n", y, x);
return 0;
}