[ACCEPTED]-Finding a single number in a list-puzzle

The fastest (O(n)) and most memory efficient 8 (O(1)) way is with the XOR operation.

In 7 C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

This prints "1", which is the only one 6 that occurs once.

This works because the 5 first time you hit a number it marks the 4 num variable with itself, and the second 3 time it unmarks num with itself (more or 2 less). The only one that remains unmarked 1 is your non-duplicate.

By the way, you can expand on this idea 17 to very quickly find two unique numbers among 16 a list of duplicates.

Let's call the unique 15 numbers a and b. First take the XOR of 14 everything, as Kyle suggested. What we 13 get is a^b. We know a^b != 0, since a != b. Choose 12 any 1 bit of a^b, and use that as a mask 11 -- in more detail: choose x as a power of 10 2 so that x & (a^b) is nonzero.

Now split 9 the list into two sublists -- one sublist 8 contains all numbers y with y&x == 0, and 7 the rest go in the other sublist. By the 6 way we chose x, we know that a and b are 5 in different buckets. We also know that 4 each pair of duplicates is still in the 3 same bucket. So we can now apply ye olde 2 "XOR-em-all" trick to each bucket independently, and 1 discover what a and b are completely.

Bam.

O(N) time, O(N) memory

HT= Hash Table

HT.clear() go over the list 11 in order for each item you see

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

at the end, the 10 item in the HT is the item you are looking 9 for.

Note (credit @Jared Updike): This system 8 will find all Odd instances of items.

comment: I 7 don't see how can people vote up solutions 6 that give you NLogN performance. in which 5 universe is that "better" ? I am even more 4 shocked you marked the accepted answer s 3 NLogN solution...

I do agree however that 2 if memory is required to be constant, then 1 NLogN would be (so far) the best solution.

Kyle's solution would obviously not catch 19 situations were the data set does not follow 18 the rules. If all numbers were in pairs 17 the algorithm would give a result of zero, the 16 exact same value as if zero would be the 15 only value with single occurance.

If there 14 were multiple single occurance values or 13 triples, the result would be errouness as 12 well.

Testing the data set might well end 11 up with a more costly algorithm, either 10 in memory or time.

Csmba's solution does 9 show some errouness data (no or more then 8 one single occurence value), but not other 7 (quadrouples). Regarding his solution, depending 6 on the implementation of HT, either memory 5 and/or time is more then O(n).

If we cannot 4 be sure about the correctness of the input 3 set, sorting and counting or using a hashtable 2 counting occurances with the integer itself 1 being the hash key would both be feasible.

I would say that using a sorting algorithm 7 and then going through the sorted list to 6 find the number is a good way to do it.

And 5 now the problem is finding "the best" sorting 4 algorithm. There are a lot of sorting algorithms, each 3 of them with its strong and weak points, so 2 this is quite a complicated question. The 1 Wikipedia entry seems like a nice source of info on that.

Implementation in Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

0

You need to specify what you mean by "best" - to 10 some, speed is all that matters and would 9 qualify an answer as "best" - for others, they 8 might forgive a few hundred milliseconds 7 if the solution was more readable.

"Best" is 6 subjective unless you are more specific.

That 5 said:

Iterate through the numbers, for each 4 number search the list for that number and 3 when you reach the number that returns only 2 a 1 for the number of search results, you 1 are done.

Seems like the best you could do is to iterate 16 through the list, for every item add it 15 to a list of "seen" items or else remove 14 it from the "seen" if it's already there, and 13 at the end your list of "seen" items will 12 include the singular element. This is O(n) in 11 regards to time and n in regards to space 10 (in the worst case, it will be much better 9 if the list is sorted).

The fact that they're 8 integers doesn't really factor in, since 7 there's nothing special you can do with 6 adding them up... is there?

Question

I don't understand 5 why the selected answer is "best" by any 4 standard. O(N*lgN) > O(N), and it changes 3 the list (or else creates a copy of it, which 2 is still more expensive in space and time). Am 1 I missing something?

Depends on how large/small/diverse the numbers 3 are though. A radix sort might be applicable 2 which would reduce the sorting time of the 1 O(N log N) solution by a large degree.

The sorting method and the XOR method have 12 the same time complexity. The XOR method 11 is only O(n) if you assume that bitwise 10 XOR of two strings is a constant time operation. This 9 is equivalent to saying that the size of 8 the integers in the array is bounded by 7 a constant. In that case you can use Radix 6 sort to sort the array in O(n).

If the numbers 5 are not bounded, then bitwise XOR takes 4 time O(k) where k is the length of the bit 3 string, and the XOR method takes O(nk). Now 2 again Radix sort will sort the array in 1 time O(nk).