Author Topic: Mild Nerdsnipe  (Read 1368 times)

0 Members and 1 Guest are viewing this topic.

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17664
  • MHNATY ~~~~~
    • View Profile
    • sidoh
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.

Offline Camel

  • Hero Member
  • *****
  • Posts: 1705
    • View Profile
    • BNU Bot
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!

Offline Camel

  • Hero Member
  • *****
  • Posts: 1705
    • View Profile
    • BNU Bot
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!

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17664
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Mild Nerdsnipe
« Reply #3 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.
« Last Edit: July 06, 2008, 01:09:15 pm by Sidoh »

Offline Camel

  • Hero Member
  • *****
  • Posts: 1705
    • View Profile
    • BNU Bot
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!