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.

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.

Take the first number in array. XOR it with the second number. save
the result and XOR the result with the third number. Repeat this
until you reach the last element. Final result of XOR is the number
that doesn't have any duplicate.
(Reason is that, when XOR the number with itself result is always zero )

> 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 you have a topical question about C?

junky_fel...@yahoo.co.in wrote:
> Take the first number in array. XOR it with the second number. save
> the result and XOR the result with the third number. Repeat this
> until you reach the last element. Final result of XOR is the number
> that doesn't have any duplicate.

This is only guaranteed if the integer type in question is unsigned.

> (Reason is that, when XOR the number with itself result is always zero)

With signed integers, it's possible to produce negative zeros
or trap representations or along the way.

-- 
Peter

step 1 : sort the array using qsort O(nlogn)

step 2: for(i=0;i<n-1;i+=2)
           {
               if(a[i]!=a[i+1])
                    return  a[i];
            }
           return a[n];

complexity of step 2 is (n-1)/2 .. ie. O(n) [ we search for two
consequetive numbers to be equal, if we do not find such a number we
return it. this is done for alternate indexes in the array and if all
of them match, the last element is returned.

total time complexity :
O(nlogn + n) = O(n)

please point out if i have done mistake in calculating the complexity.

Peter Nilsson 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 you have a topical question about C?
>
> junky_fel...@yahoo.co.in wrote:
> > Take the first number in array. XOR it with the second number. save
> > the result and XOR the result with the third number. Repeat this
> > until you reach the last element. Final result of XOR is the number
> > that doesn't have any duplicate.
>
> This is only guaranteed if the integer type in question is unsigned.
>
> > (Reason is that, when XOR the number with itself result is always zero)
>
> With signed integers, it's possible to produce negative zeros
> or trap representations or along the way.
> 
> -- 
> Peter

Anyway I think his solution is very cool.

In article <1118384946.849837.192230@g49g2000cwa.googlegroups.com>,
sunny <sunnynnus@gmail.com> wrote:
>
>
>step 1 : sort the array using qsort O(nlogn)
>
>step 2: for(i=0;i<n-1;i+=2)
....
>total time complexity :
>O(nlogn + n) = O(n)
>
>please point out if i have done mistake in calculating the complexity.

You have done a mistake (or two) in calculating the complexity.

1. O(n log n) + O(n) = O(n log n)
2. There is no guarantee that qsort is O(n log n) anyway.
-- 
7842++

On Thu, 09 Jun 2005 23:29:06 -0700, sunny wrote:

....

> total time complexity :
> O(nlogn + n) = O(n)

nlogn is a higher complexity than n so O(nlogn +  n) is the same as
O(nlogn)

Lawrence

On Thu, 09 Jun 2005 22:50:10 -0700, Peter Nilsson 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 you have a topical question about C?
> 
> junky_fel...@yahoo.co.in wrote:
>> Take the first number in array. XOR it with the second number. save
>> the result and XOR the result with the third number. Repeat this
>> until you reach the last element. Final result of XOR is the number
>> that doesn't have any duplicate.
> 
> This is only guaranteed if the integer type in question is unsigned.

Any integer type is OK as long as the values are all non-negative. You
could adapt the algorithm for negative numbers by transforming the values
to positive ones first, XORing and transforming the result back. You don't
have to fit the transformed value in just one variable if you are worried
about ranges.

>
>> (Reason is that, when XOR the number with itself result is always zero)
> 
> With signed integers, it's possible to produce negative zeros
> or trap representations or along the way.

For XOR the result will be valid and non-negative if the 2 operands are.
The only thing you might have to consider if whether 0 could be
represented by a negative zero on implementations which support that.

Lawrence

sunny wrote:
> step 1 : sort the array using qsort O(nlogn)
> 
> step 2: for(i=0;i<n-1;i+=2)
>            {
>                if(a[i]!=a[i+1])
>                     return  a[i];
>             }
>            return a[n];
> 
> complexity of step 2 is (n-1)/2 .. ie. O(n) [ we search for two
> consequetive numbers to be equal, if we do not find such a number we
> return it. this is done for alternate indexes in the array and if all
> of them match, the last element is returned.
> 
> total time complexity :
> O(nlogn + n) = O(n)
> 
> please point out if i have done mistake in calculating the complexity.
> 

Suppose a and b be sequences. We say that a is O(b) if a / b
is bounded, i.e. there exists a number M for which for all n

    a(n) / b(n) < M.

You claim that

    a(n) is O(n log n + n) implies a(n) is O(n),

but that is not true, since

    a(n) / n is not less than a(n) / (n log n + n).


-- August