Subj : Re: puzzle
To   : comp.programming
From : Christopher Barber
Date : Fri Jul 01 2005 02:33 pm

spinoza1111@yahoo.com 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.
>>
>>Note that word "INTEGER".  It doesn't HAVE to work for floating point
>>systems!
> 
> Real programming is not a matter of solutions isomorphic to problems,
> and responding to one problem as expressed "today" with a solution
> tuned to that problem.
> 
> Instead, the real programmer recognizes, as an aura around the user's
> expression of the problem, a genuine class of problems to which today's
> problem will evolve.

Often solving the problem as stated is exactly what is needed in "real 
programming", but you are right that it can be important to recognize
how to generalize your solutions.

> He thus eschews solutions which are overly tuned, in a trickster
> fashion, to one empirical property of the problem such as "integers".

I don't see how "integers" is an empirical property of a problem.  No 
experimentation was needed.  The problem stated the data type.  In
the real programming world, you usually know the data types of your
input in advance.  You also neglect that the more significant limitiation to 
the problem definition is not that it specified integers but that it specified 
that each value appears exactly twice except for one unique value, this latter
property seems much more strange than limiting the data set to integers.

In any case, even if you generalize the problem there are a number of other
O(n) and O(n log n) solutions that do not require use of XOR.

The solution you posted was no better than O(n^3) and is obviously too 
expensive to use unless n is very small. It is also more expensive and takes 
more code than the brute-force O(n^2) solution, so there is no reason to use 
it even when n is small.  No "real world" programmer would use such an 
algorithm, so it is strange to find you lecturing us about "real programming".

 > With which I think I shall end my participation in this thread.

I rather doubt it.

- Christopher

.