How to find unpaired element in unsorted array with clear O(n) runtime and memory?

Question

Yandex interview question: "You have been given array where all elements except 1 are repeated twice. You should find this unpaired element. Example: {2, 5, 2, 3, 4, 4, 5}. <- Here answer is 3. Elements are not grater than 10^18.

My solution was to use HashMap for storing count of times each element enters in array. C++ Code below:

unordered_map<long long, long long> m;
for (int i = 0; i < n; i++) 
    m[a[i]]++;
for (int i = 0; i < n; i++) 
    if (m[a[i]] == 1) {
        cout << a[i];
        return 0;
    }

This way has O(n) complexity but uses hashmap. Interviewer said that it possible to do it without hashmap or similar data structure with clear O(n) runtime and memory. How to do this?

Answer 1

You can go for bitwise Xor since it is commutative final result will be the required answer. You just need to iterate over the array only once here is the code for it:- int res = 0; for(int i : arr) res ^= i;