Re: puzzle


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.

[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.

-Arthur
.

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: Error 3021
    ... Create proto-file names using the selected job names and storre to an array ... Save and close the document and repeat the loop ... Dim strJobsAs String, strDocsAs String, varValsAs _ ...
    (microsoft.public.access.modulesdaovba)
  • RE: Error 3021
    ... Kevin Backmann ... Create proto-file names using the selected job names and storre to an array ... Save and close the document and repeat the loop ... Dim strJobsAs String, strDocsAs String, varValsAs _ ...
    (microsoft.public.access.modulesdaovba)
  • RE: Error 3021
    ... Create proto-file names using the selected job names and storre to an array ... Save and close the document and repeat the loop ... Dim strJobsAs String, strDocsAs String, varValsAs _ ...
    (microsoft.public.access.modulesdaovba)
  • Re: Displaying a large amount of data quickly (VB6)
    ... >>> involving a loop of VB code would be too slow. ... but I'd sure be interested to know if that StringBuilder ... Array elements: 25000 ... Array construction: 17 ...
    (microsoft.public.vb.controls)