Clan x86

General Forums => Academic / School => Math and Other Problems => Topic started by: Sidoh on July 06, 2008, 01:01:45 am

Title: Mild Nerdsnipe
Post by: Sidoh on July 06, 2008, 01:01:45 am
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.
Title: Re: Mild Nerdsnipe
Post by: Camel on July 06, 2008, 12:53:26 pm
EZ-cakes.

Code: [Select]
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
Title: Re: Mild Nerdsnipe
Post by: Camel on July 06, 2008, 12:59:48 pm
It just occurred to me that I misread the question.

No matter; simply iterate over the heap and look for a value of 1.
Title: Re: Mild Nerdsnipe
Post by: Sidoh on July 06, 2008, 01:06:05 pm
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.
Title: Re: Mild Nerdsnipe
Post by: Camel on July 06, 2008, 09:19:04 pm
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]
int findSingleton(int array[]) {
    int result = 0;
    for(int value : array)
        result ^= value;
    return result;
}
[/spoiler]