COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### puzzle #3

• Email
• Follow

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

```
 0
Reply ranveerkunal (24) 6/10/2005 4:02:00 AM

See related articles to this posting

```
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 )

```
 0
Reply junky_fellow (377) 6/10/2005 5:31:34 AM

```> 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

```
 0
Reply airia (1802) 6/10/2005 5:50:10 AM

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

```
 0
Reply sunnynnus (6) 6/10/2005 6:29:06 AM

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

```
 0
Reply prawit.c (49) 6/10/2005 7:17:01 AM

```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++
```
 0
Reply anon7843 (142) 6/10/2005 5:21:05 PM

```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
```
 0
Reply lknews (877) 6/10/2005 6:27:30 PM

```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

>
>> (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

```
 0
Reply lknews (877) 6/10/2005 6:36:32 PM

```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

```
 0
Reply fusionfive (563) 6/14/2005 1:45:41 PM

8 Replies
42 Views

Similar Articles

12/10/2013 5:25:20 PM
page loaded in 40061 ms. (0)

Similar Artilces:

dvips puzzle
Hello Gurus, When I started using latex I was able to print a dvi file F by dvips F Later, after installing other things (OS etc) I had to do it so: dvips -P color F. Now, with suse 9.1 linux and cups I seem to have to do something like dvips F gv F.ps and then print via gv (ghost view). Why is that? Is there a better way? Any suggestions gratefully received. Ivan. ivan danicic wrote: > Hello Gurus, When I started using latex I was able to print a dvi file F by > dvips F this is because in your default dvips config, the output was sent to the def

small array of cells puzzle
Just wondering if anyone had any cute ways of producing an N x M cell array in which every entry was the empty cell? I have come up with two ways so far, but suspect there might be some nicer or more interesting ways: R = repmat({{}}, N, M); %bleh R = cell(N,M); R(:) = {{}}; %more efficient bleh If anyone happens to be wondering -why- : I'm building an empty struct from a cellstr of field names, fieldmix = [stnames, repmat({{}},length(stnames),1)] .'; thestruct = struct( fieldmix{:} ); If you try the more obvious fieldmix = [stnames, cell(length(stnames),1)] .';

Re:Printer Puzzle
Hi all Further to my posting last week: thanks to those who responded with suggestions. Sadly I'm no further forward with an answer. I've tried all the cleaning functions from the printer - everythings seems OK. I've tried copying pictures from my card reader (which shares the parallel port) & that seems to work OK. I've swopped cables & even tried out a similar printer - but both are as dead as dodos, I have to resort to converting everything using Easiwriter and then taking stuff into school to print on my laptop - tedious to say the least. Is there anything else I ca

Re: Programming Puzzle
> �mjsfromynr@sancharnet.in (Jatinder)�n > I found these questions on a web site and wish to share with all of u > out there,Can SomeOne Solve these Porgramming puzzles. > Programming Puzzles > Some companies certainly ask for these things. Specially Microsoft. > Here are my favorite puzzles. Don't send me emails asking for the > solutions. > Q1 Write a "Hello World" program in 'C' without using a semicolon. My solution #include <stdio.h> int main( void ) { if ( puts( "Hello World" ) ) {} } > Q5 C/C++ : Multiply x by 7 wit