# Re: puzzle

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.

Consider that if you choose a random number or the midpoint from the
array and search (in a single loop) in both directions before and after
that number for its unique mate, you will either discover that it is
the unique number U (when your search ends "unsuccessfully") or else
you will have a very interesting data structure: a group of THREE array
segments

a[0]..a[i], a[i+2]..a[i+j+2], a[i+j+4]..a[arraySize-1]

when a[i+1] = a[i+j+3].

I'll assume you can DELETE elements. DELETE a[i+1] and a[i+j+3]. Choose
the midpoint of the remaining elements and repeat...until you have one
element in the array. In the worst case this will be U, but usually you
will find U before you remove all entries except U.

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.

The major flaw in this algorithm is its blithe assumption that DELETE
is atomic and fast.

As long as we're free to represent the array as a collection in a
modern language that supports collections this isn't a problem. As long
as the collection delete uses a bidirectional linked list delete is
fast. Or, the array can be represented as a bidirectional linked list.
If it is provided as an array of adjacent entries it can be copied to a
linked list in O(n) time making the time close to O(n) by a constant
factor.

But suppose the array is a classic array, and delete involves moving
elements. Each bidirectional search will still partition the array as
above.

Select the midpoint of the middle partition, or the last entry of the
first partition (if the middle partition is empty) or the midpoint of
the last partition (if the first and middle partitions are empty where
a[0]=a[1].

Repeat the search. You will unnecessarily examine previously found
pairs of numbers. Boo hoo. They will never match the new midpoint
because the problem precondition declares that entries only occur
twice, except for U.

Definitely not O(n) if DELETE is not supported and for some stupid
reason you can't just copy to a linked list, but "optimistic" for
reasonable arraySize because U will be found sooner and not later. The
execution time formula will be the arraySize raised to the second
power, but divided by two.

"The idea of the method of limits is simple and amounts to the
following. In order to determine the exact value of a certain
magnitude, we first determine not the magnitude itself but some
approximation to it. However, we make not one approximation but a whole
series of them, each more accurate than the last. Then from examination
of this chain of approximation itself, we uniquely determine the exact
value of the magnitude. By this method, *** which is in essence a
profoundly dialectical one ***, we obtain a fixed constant as a result
of a process or motion."

- A. D. Aleksandrov, A. N. Kolmogorov and M. A. Lavrent'ev,
MATHEMATICS: ITS CONTENT, METHODS AND MEANING (Matematika, ee
soderzhanie metody i znachine). Original English edition: MIT Press,
Cambridge MA. Dover 1999.

.

• References:

## Relevant Pages

• Re: How to write Property Let for the single elements of an array
... the array) as well as the array size, an increment, and load it all ... Private pYValues() As Double ... Private ArrayIndex As Long ... Private ArraySize As Long ...
(microsoft.public.excel.programming)
• Re: Marshalling Array In/Out C++ COM Control
... using Marshal.AllocCoTaskMem to allocate memory for the array, ... VARIANT_BOOL DetectCode(long* codeArray, short* arraySize) ... "Mattias Sjögren" wrote: ...
(microsoft.public.dotnet.framework.interop)
• Dynamic array
... i wanted that it automatically calcule the size of the array, ... Dim anotherIteration As Boolean ... Dim arraySize As Integer ...
(microsoft.public.excel.programming)
• Re: Sorting a string array containing combinations
... simultaneously create another array which does not contain occurrences of x1 in it. ... Dim TempArrayAs Long ... Dim WithX(1 To Rows, ArraySize) As Long ... Dim CountWith As Long, CountWithout As Long ...
(microsoft.public.excel.programming)
• Re: Marshalling Array In/Out C++ COM Control
... I am having this exact problem. ... > using Marshal.AllocCoTaskMem to allocate memory for the array, ... > When the method is called, codeArray is intialized, and contains all 0's. ... > arraySize is the number of elements in codeArray. ...
(microsoft.public.dotnet.framework.interop)