In a list of numbers, every number appears exactly twice except one, which appears once. Print that one. Solve it with XOR, in one pass and with no extra array.
What to build
An XOR program that finds the one number without a partner.
Requirements
- Use one pass through the numbers.
- Use no array and no sorting.
- Print the number left over.
Input
A line with n (odd, 1 ≤ n ≤ 999), then n whole numbers from 0 to 1 000 000 000.
Output
The number that appears only once.
Constraints
n is odd, 1 ≤ n ≤ 999, and each number is from 0 to 1 000 000 000.
Example
Input:
5
4 1 2 1 2
Output:
4
Why it works
x ^ x is 0, and XOR does not depend on order, so every pair cancels and only the single number remains.
Examples
Example 1 · Input
5 4 1 2 1 2
Expected output
4
Example 2 · Input
1 99
Expected output
99
Hints
Hint 1
x ^ x is 0, and x ^ 0 is x.
Hint 2
XOR does not care about order, so XOR-ing all the numbers cancels every pair.
Hint 3
Start with result = 0 and do result ^= v for every number.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, v, result = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &v);
result ^= v;
}
printf("%d\n", result);
return 0;
}