puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: CBFalconer on 10 Jul 2005 12:11 spinoza1111(a)yahoo.com wrote: > .... snip ... > in this thread, I have repeatedly acknowledged that I did not have > enough erudition to think of, or in my case from grad school > remember, the XOR solution. .... snip further pointless erudition ... FYI, the entire secret of the XOR solution is exposed in the following truth table: a b XOR(a,b) = = ======== F F F F T T T F T T T F Some have been known to learn this without attending grad school. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson
From: Joe Seigh on 10 Jul 2005 13:02 CBFalconer wrote: > spinoza1111(a)yahoo.com wrote: > > ... snip ... > >>in this thread, I have repeatedly acknowledged that I did not have >>enough erudition to think of, or in my case from grad school >>remember, the XOR solution. > > ... snip further pointless erudition ... > > FYI, the entire secret of the XOR solution is exposed in the > following truth table: > > a b XOR(a,b) > = = ======== > F F F > F T T > T F T > T T F > > Some have been known to learn this without attending grad school. > 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. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software.
From: Willem on 10 Jul 2005 13:37 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) ? 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 13:47 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) -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software.
From: Willem on 10 Jul 2005 16:52
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 ? 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 |