Find algorithm task

[Duthomhas]

Heh, that adds an important restriction:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

...which in my mind make this problem unsolvable.

[frek]

@lastchance
>[i]in your last code (it's getting quite complex to remember which example you are referring to) [/i]
The exercise is written right before the solutions! That's a new one.
Each time I try to create two solutions and post it here for evaluation and learning new stuff.

>Unless you are doing a counting sort (not realistic here), both creating a set and sorting are going to have that complexity.
I didn't get this! Why sorting is unrealistic here, please?

[lastchance]

@frek, read carefully! I didn't say "sorting" was unrealistic; I said that a specific type of sort - "counting sort" was unrealistic.

"Which example you are referring to" - @frek, you've posted THREE different examples in the same thread of this forum. If you want different examples ... use different forum threads.

[lastchance]

So, addressing the question that @Frek posed here:
http://www.cplusplus.com/forum/general/282480/#msg1222830

and using the link that @againtry provided:
https://stackoverflow.com/questions/43058889/how-to-improve-the-code-to-return-the-unpaired-element

and cheating mercilessly by reading the answers in that link, we get (in c++):

#include <iostream>
#include <vector>
using namespace std;

int unpaired( const vector<int> &V )
{
   int result = 0;
   for ( auto e : V ) result ^= e;
   return result;
}

int main()
{
   vector<int> V = { 8, 5, 6, -2, 8, -2, 6 };
   cout << unpaired( V );
}

which is, indeed, O(N) in time and O(1) in space.

Credit to whoever wrote the original answer in some other language on Stack Overflow. (Amazing that it wasn't accepted as the preferred answer there.)

[Duthomhas]

LOL, nice. I had forgotten about the specialist integer bit-twiddling possibility.