Find only unique number in vector

Question

Find the number occuring only once in a vector. Given a vector A, containing N pairs (1, 1, 2, 3, 3 ... etc.) and one unique number, find and return the one unique number.

I wrote the following code for this problem.

As I don't have a lot of experience I would be grateful for any kind of feedback regarding my solution so it can be improved.

#include <iostream>
#include <unordered_map>
#include <vector>
uint32_t find_unique(std::vector<uint32_t> &A)
{
 std::unordered_map<uint32_t, uint32_t> seen;
 for (const auto &it : A)
 {
 if (++seen[it] > 1)
 {
 seen.erase(it);
 }
 }
 return seen.begin()->first;
}
int main()
{
 std::vector<uint32_t> v{1, 1, 6, 2, 2, 3, 3, 4, 4, 5, 5};
 std::cout << find_unique(v) << "\n";
 return 0;
}

• Toby Speight: @Loki, the question states "N pairs" and one unique member. If I'd read only the title, I'd have agreed with you.

Answer 1

You can use a more efficient algorithm. It's clear that the unique value is equal to the xor of all numbers in the vector. One can write a nice one-liner to compute it:

std::accumulate(v.begin(), v.end(), (uint32_t)0, [](uint32_t a, uint32_t b) { return a ^ b; })

The time complexity is the same (as a hash table works in O(1) on average), but this code is likely to work faster in practice. It also requires O(1) extra memory, while your solution needs O(n), so it's more space efficient.

I'd also say that your code is little bit confusing (it inserts keys implicitly via [] operator but erases them explicitly). It took me a while to figure out what's going on. I think that the solution with a set is a little bit more clear as it makes all insertions and deletions explicitly:

unordered_set<uint32_t> seen;
for (const auto& elem : v) {
 if (seen.count(elem))
 seen.erase(elem);
 else
 seen.insert(elem);
}
return *seen->begin();

You can also omit return 0 in the main function (it returns 0 by default, anyway).

• miscco: The part about "\n" seems wrong. std::endl includes a flush of the stream which is nearly always unnecessary.
• kraskevich: @miscco You're right, it doesn't localize the line separator, so it's useless. I removed this part of my answer.
• Loki Astari: @kraskevich: Just for reference. The '\n' character is also converted to platform specific line termination sequence.
• kraskevich: @LokiAstari The post says that all other numbers form pairs, which is the same thing as an even number of occurrences.
• yuri: The XOR solution is pretty nifty.