Mild Nerdsnipe

[Sidoh]

A friend at work got me with this one, but luckily I forgot about it because I got distracted with work.  When he asked me about it the next morning, I thought about it for a few minutes and had an answer. :)

You're given a list of arbitrary length where each element in the list is repeated exactly once except for one value in an arbitrary location.  Your task is to find the value.  You're allowed to pass over the list exactly once and use O(1) (constant, i.e. the amount of space you're using doesn't depend on the size of the list) extra space.

[Camel]

EZ-cakes.

Code Select Expand

int findDuplicate(int array[]) {
    int[] heap = new int[2^sizeof(int)]; // assume heap is all zeroes
    for(int value : array) {
        if(heap[value]++ > 0)
            return value;
    }
    throw exception;
}

edit: code tag

[Camel]

It just occurred to me that I misread the question.

No matter; simply iterate over the heap and look for a value of 1.

[Sidoh]

Yuck. :P

No, the answer isn't gross.  There's a pseudo-clever solution.

Also notice that the data in the list aren't necessarily of type int.  You don't have the upper bound you've inferred.

[Camel]

That code works with any fixed-width type, and meets all of the criteria you gave.

However, it did just occur to me that there's a way to eliminate the heap due to the contraint that the non-singletons appear an even number of times. This forum should definitely have spoiler tags!

[spoiler]

Code Select Expand

int findSingleton(int array[]) {
    int result = 0;
    for(int value : array)
        result ^= value;
    return result;
}[/spoiler]