puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Joe Seigh on 10 Jul 2005 17:33 Willem wrote: > Joe wrote: > ) Willem wrote: > )> Joe wrote: > )> ) To make things interesting, this problem should be reposed as, > )> ) you have a unordered sequence of the numbers 0 to n with one > )> ) number missing and the others appearing only once. Find two > )> ) O(n) ways of determining the missing number. > )> > )> O(n) time and how much memory ? O(1) ? O(n) ? > )> > ) O(1) > > Well, I can only think of one solution offhand, with a few variations. > I'm assuming you mean fundamentally different solutions ? > Well, the standard solution for one. This is a standard whiteboard question. This is also a slightly reformulated version of the problem being discussed already. A slight hint. n should be an odd number but it doesn't really matter. You can solve it if n is even. You can also go for a O(2n) solution if that makes it any easier. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software.
From: Richard Harter on 10 Jul 2005 17:35 On Sun, 10 Jul 2005 20:52:12 +0000 (UTC), Willem <willem(a)stack.nl> wrote: >Joe wrote: >) Willem wrote: >)> Joe wrote: >)> ) To make things interesting, this problem should be reposed as, >)> ) you have a unordered sequence of the numbers 0 to n with one >)> ) number missing and the others appearing only once. Find two >)> ) O(n) ways of determining the missing number. >)> >)> O(n) time and how much memory ? O(1) ? O(n) ? >)> >) O(1) > >Well, I can only think of one solution offhand, with a few variations. >I'm assuming you mean fundamentally different solutions ? Method 1: Determine the xor of the numbers 0...n, then xor the sequence. Xor the two results to get the missing number. Method 2: Determine the sum of the numbers 0...n, then the sum of the sequence. The difference of the two sums is the missing number. To avoid overflow/underflow do the sums module n+1. Method 3: If you can reorder the sequence, partition it into two halves (the criteria can be size, or odd/even), determine which partition is missing an element, and repeat as needed. For extra credit, give a method not a simple variation. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: Willem on 10 Jul 2005 17:41 Richard wrote: ) Method 1: Determine the xor of the numbers 0...n, then xor the ) sequence. Xor the two results to get the missing number. ) ) Method 2: Determine the sum of the numbers 0...n, then the sum of the ) sequence. The difference of the two sums is the missing number. To ) avoid overflow/underflow do the sums module n+1. I would call those variations on a theme, to be honest. ) Method 3: If you can reorder the sequence, partition it into two ) halves (the criteria can be size, or odd/even), determine which ) partition is missing an element, and repeat as needed. Ah, should have thought of that one, especially given the whole discussion with the conclusion that it is, in fact, an O(n) solution. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT
From: Joe Seigh on 10 Jul 2005 17:45 Richard Harter wrote: > On Sun, 10 Jul 2005 20:52:12 +0000 (UTC), Willem <willem(a)stack.nl> > wrote: > > >>Joe wrote: >>) Willem wrote: >>)> Joe wrote: >>)> ) To make things interesting, this problem should be reposed as, >>)> ) you have a unordered sequence of the numbers 0 to n with one >>)> ) number missing and the others appearing only once. Find two >>)> ) O(n) ways of determining the missing number. >>)> >>)> O(n) time and how much memory ? O(1) ? O(n) ? >>)> >>) O(1) >> >>Well, I can only think of one solution offhand, with a few variations. >>I'm assuming you mean fundamentally different solutions ? > > > Method 1: Determine the xor of the numbers 0...n, then xor the > sequence. Xor the two results to get the missing number. That's the O(2n) solution. > > Method 2: Determine the sum of the numbers 0...n, then the sum of the > sequence. The difference of the two sums is the missing number. To > avoid overflow/underflow do the sums module n+1. That's the standard solution. > > Method 3: If you can reorder the sequence, partition it into two > halves (the criteria can be size, or odd/even), determine which > partition is missing an element, and repeat as needed. O(2n) but probably not O(1) size in the sense we're looking for. Good solution of that type. Avoids a sort. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software.
From: Willem on 10 Jul 2005 19:02
)> Method 1: Determine the xor of the numbers 0...n, then xor the )> sequence. Xor the two results to get the missing number. Joe wrote: ) That's the O(2n) solution. Are you sure it takes O(n) time to find the xor of the numbers 0..n ? Anyway, this and the solution below are variations on the same theme. )> Method 2: Determine the sum of the numbers 0...n, then the sum of the )> sequence. The difference of the two sums is the missing number. To )> avoid overflow/underflow do the sums module n+1. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT |