6
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ @Loki, the question states "N pairs" and one unique member. If I'd read only the title, I'd have agreed with you. \$\endgroup\$ – Toby Speight May 22 '17 at 10:52
8
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The part about "\n" seems wrong. std::endl includes a flush of the stream which is nearly always unnecessary. \$\endgroup\$ – miscco May 21 '17 at 16:54
  • \$\begingroup\$ @miscco You're right, it doesn't localize the line separator, so it's useless. I removed this part of my answer. \$\endgroup\$ – kraskevich May 21 '17 at 17:12
  • 1
    \$\begingroup\$ @kraskevich: Just for reference. The '\n' character is also converted to platform specific line termination sequence. \$\endgroup\$ – Martin York May 22 '17 at 1:55
  • \$\begingroup\$ @LokiAstari The post says that all other numbers form pairs, which is the same thing as an even number of occurrences. \$\endgroup\$ – kraskevich May 22 '17 at 7:09
  • \$\begingroup\$ The XOR solution is pretty nifty. \$\endgroup\$ – yuri May 23 '17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.