puzzle

[Darius]

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.

 

[junky_fellow]

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 )

 

[Peter Nilsson]

Do you have a topical question about C?

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.

 

[sunny]

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

step 2: for(i=0;i<n-1;i+=2)
{
if(a!=a[i+1])
return a;
}
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.

 

[Prawit Chaivong]

Do you have a topical question about C?



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


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

Anyway I think his solution is very cool.

 

[Anonymous 7843]

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.

 

[Lawrence Kirby]

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

 

[Lawrence Kirby]

Do you have a topical question about C?



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.

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

 

[akarl]

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

step 2: for(i=0;i<n-1;i+=2)
{
if(a!=a[i+1])
return a;
}
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