puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Richard Harter on 11 Jul 2005 15:07 On Sun, 10 Jul 2005 21:41:39 +0000 (UTC), Willem <willem(a)stack.nl> wrote: >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. Fair enough. Here is another variation on the theme: If n is odd set sum = - (n+1)/2. Loop through the numbers. Add the odd ones to sum and subtract the even ones from sum. Conversely if n is even set sum = -n/2. Loop through the numbers. Add the even ones to sum and subtract the odd ones from sum. At the end sum contains the missing number. > >) 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. And for a third method we can sort the sequence. For this data sorting can be done with O(n) time and O(1) space. A variation on this theme that is not quite sorting runs as follows: Without loss of generality we can use notation that treats the sequence as being in an array. Let A be the array, let indexing be 0 based, and let a[i] be the i'th element in A. As pseudocode: foreach i in 0...n-1 select A[i] =? i : nil A[i] =? n : nil else : begin j = i k = A[i] A[i] = n repeat j = k k = a[j] A[j] = j until (k =? n) end else end select end foreach foreach i in 0...n-1 if (A[i] =? n) return i end foreach return n The general idea here is that the data set regarded as a permutation has one broken cycle. The regular cycles are simply permuted. The broken cycle is permuted in pieces. In the end A[i] = i except for the missing item j and there A[j] = n. Loop through the array, i = 0...n. If A[i] = i or A[i] = n do nothing, else do: 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: John Smith on 13 Jul 2005 13:47 spinoza1111(a)yahoo.com wrote: > Puzzles suck. The ability to consider alternatives and constraints is > what's important. They also produce bad feeling in a classroom because > of necessity they make only one student look "smart". Thereby reducing the "self-esteem" of all the others -- a major violation of political correctness as applied to education. -JS
From: blmblm on 14 Jul 2005 05:27 In article <42D13B68.CB9B3125(a)yahoo.com>, CBFalconer <cbfalconer(a)worldnet.att.net> 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. Well .... If you're saying that anyone who knows the XOR operator should have come up with the XOR-based solution to the puzzle, I don't think that's true. I think it also requires a bit of cleverness, or trickiness, or a certain mindset, or perhaps just having previously encountered similar puzzle solutions. -- | B. L. Massingill | ObDisclaimer: I don't speak for my employers; they return the favor.
From: Michael Wojcik on 15 Jul 2005 12:36 In article <3jpo8qFr9cu5U1(a)individual.net>, blmblm(a)myrealbox.com writes: > In article <1121343478.738610.306570(a)o13g2000cwo.googlegroups.com>, > <spinoza1111(a)yahoo.com> wrote: > > >However, I've been posting and reading in all probability far > >longer than you punks, > > Maybe, maybe not. Hard to say if you don't provide some specifics > (such as an approximate date when you discovered Usenet). The earliest post I could find is 4921(a)pucc.Princeton.EDU, made on 11 April 1988. That means he's been posting longer than *this* punk, but perhaps not "far longer", though that's a subjective matter. The difference is about 18% at this point. Certainly some of the other punks have been around longer than that; there are plenty who've been participating since before the Great Renaming. Whether any of them are regulars on comp.programming I don't know. -- Michael Wojcik michael.wojcik(a)microfocus.com We are subdued to what we work in. (E M Forster)
From: spinoza1111 on 17 Jul 2005 21:56
Michael Wojcik wrote: > In article <3jpo8qFr9cu5U1(a)individual.net>, blmblm(a)myrealbox.com writes: > > In article <1121343478.738610.306570(a)o13g2000cwo.googlegroups.com>, > > <spinoza1111(a)yahoo.com> wrote: > > > > >However, I've been posting and reading in all probability far > > >longer than you punks, > > > > Maybe, maybe not. Hard to say if you don't provide some specifics > > (such as an approximate date when you discovered Usenet). > > The earliest post I could find is 4921(a)pucc.Princeton.EDU, made on > 11 April 1988. That means he's been posting longer than *this* > punk, but perhaps not "far longer", though that's a subjective > matter. The difference is about 18% at this point. Sounds correct. Prior to that time I participated in IBM VM/CMS networks which converged around that time with the Internet. My first use of email was in 1981. > > Certainly some of the other punks have been around longer than that; > there are plenty who've been participating since before the Great > Renaming. Whether any of them are regulars on comp.programming I > don't know. > Indeed. But I ain't no spring chicken. > -- > Michael Wojcik michael.wojcik(a)microfocus.com > > We are subdued to what we work in. (E M Forster) |