Find single int among vector of duplicates in c++

Question

I am writing a function in C++ that will evaluate a vector with n integers. Every integer has one duplicate value somewhere in the vector with the exception of one single integer that has NO duplicates. The function should return that one int with no duplicate values in the array.

I managed to make a working function that I think runs in either O(nlogn) time or in O(n^2), I'm not sure which. I need the function to run in O(n) time, how can I change my function to achieve such run time?

int singleNumber(vector<int>& nums)
{
    int s = nums.size();

    for (int i = 0; i < s; i++)
    {
        int current = i;  // current int in vector being evaluated
        bool f1 = false, f2 = false;

        for (int j = 0; j < s; j++)
        {
            if (current == nums[j] && !f1)  // if one instance of current is found
                f1 = true;
            else if (f1 && current == nums[j]) // if 2nd instance of current is found
                f2 = true;
        }

        if (f1 && !f2)    // if only one instance of current is found
            return current;
    }


}

score 3 · Answer 1 · answered Jul 13 '15 at 14:11

3

I think that you'll end up with your number if you do an xor over all elements.

answered Jul 13 '15 at 14:11

Luchian Grigore

253,575
64
457
625

1

I think this question comes up regularly on SO, but it's hard to find a duplicate because the title is always different :-( – Sergey Kalinichenko Jul 13 '15 at 14:12
@dasblinkenlight same, the 1-liner was faster than searching. (i.e answer is definitely not an original idea) – Luchian Grigore Jul 13 '15 at 14:13
@dasblinkenlight case in point - the first question this links to is a dupe of a dupe... :) – Luchian Grigore Jul 13 '15 at 14:14

Find single int among vector of duplicates in c++

1 Answers1