### Author Topic: Mild Nerdsnipe  (Read 4759 times)

0 Members and 1 Guest are viewing this topic.

#### Sidoh

• Moderator
• Hero Member
• Posts: 17634
• MHNATY ~~~~~
##### Mild Nerdsnipe
« 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.

#### Camel

• Hero Member
• Posts: 1703
##### Re: Mild Nerdsnipe
« Reply #1 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
« Last Edit: July 06, 2008, 12:58:04 pm by Camel »

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

#### Camel

• Hero Member
• Posts: 1703
##### Re: Mild Nerdsnipe
« Reply #2 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.

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

#### Sidoh

• Moderator
• Hero Member
• Posts: 17634
• MHNATY ~~~~~
##### Re: Mild Nerdsnipe
« Reply #3 on: July 06, 2008, 01:06:05 pm »
Yuck.

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.
« Last Edit: July 06, 2008, 01:09:15 pm by Sidoh »

#### Camel

• Hero Member
• Posts: 1703
##### Re: Mild Nerdsnipe
« Reply #4 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]

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!