Re: puzzle



Arthur J. O'Dwyer wrote:
> On Fri, 10 Jun 2005 spinoza1111@xxxxxxxxx wrote:
> >
> > Darius wrote:
> >> ok here is a puzzle.
> >> there is an integer array whose length is odd, and all the numbers in
> >> the array appear exactly two times except one. Find the number in O(n)
> >> time. Try to do it without using any other data structure.
> >
> [...]
> >
> > Do while arraySize >= 2
> > i = floor(arraySize/2)
> > j = i-1, k = i+1
> > Do while j >= 0 or k < arraySize
> > if j>=0 and a[i]=a[j] { L = j, exit do }
> > if k<arraySize and a[i]=a[k] { L = k, exit do }
> > decrement j, increment k
> > End do
> > If j < 0 and k > arraySize return i
> > delete(i), delete(L) // Changes arraySize
> > End Do
> >
> > As long as DELETE is an atomic and fast operation this algorithm is
> > close to O(n) because the array gets smaller by two entries in the
> > worst case through its major loop, and in the worst case for the inner
> > loop (where the inner loop must search the entire array in both
> > directions) the algorithm is finished by definition.
>
> I think the above paragraph could be cleaned up to yield one of
> those clever "...and thus I am the Pope" arguments, but as it stands,
> it's too obviously confused to be convincing. Nilges' algorithm is
> O(n^2): we're doing O(n) linear searches of a linearly shrinking array.
> And yes, that's assuming DELETE is O(1), which it normally isn't.

The hell with the Pope, and King Billy too. I said "close to" because I
knew that it wasn't O(n) but practical and efficient for reasonable n.

You're doing O(n) searches, times a linearly shrinking array, only in
the worst case. N/2 the time on average it finds U. This doesn't
transform order n^2 because it divides by a constant and not N but it
is none the less a significant reduction.

>
> [snip much dissembling]
>
> The "trick" answer, which has already been posted, is definitely
> the one the OP['s instructor] was thinking of. It's actually quite
> elegant, IMHO, if not terribly useful for anything.
>
"Elegant?" I don't think so. The instructor apparently is sidetracking
the students from discussion of algorithms (which should in no case
impose a barbaric and unstated prejudice for O(n) which is a yahoo's
moral judgement masquerading as science) to the properties of Boolean
operators.

This characterization of a discussion as "dissembling" when it showed
how the theoretical classification has levels within levels explains
the 80% failure rate of enterprise systems, for it clearly shows that
some American "programmers" are invested in cheap tricks and cheap
shots and care not for that form of dialog from which real results can
be obtained.

.

Relevant Pages

  • Re: how to rotate an array
    ... What is the running time of the above algorithm? ... There will be an outer loop that loops through the number of series, ... past the bounds of the array as in charwhereas the array has length 6. ... const Iter begin, ...
    (comp.lang.cpp)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)
  • Re: counting subsets of S so that sum(S_n) = N
    ... and make my algorithm generate only unique subsets? ... and the array of boolean at one step of the algorithm is ... implementation without needing recursion. ... subsequence in W, process it and return. ...
    (comp.programming)