duplicates in array

[ak]

Is it possible to find repeated(duplicate) element in an array in
single loop ?

AK

[Walter Roberson]

In article <11********************@u36g2000prd.googlegroups.c om>,
ak <aj**********@gmail.comwrote:

>Is it possible to find repeated(duplicate) element in an array in
single loop ?

Is the array in sorted order? Are the duplicates adjacent? Will there
be exactly one element which is duplicated, or might there be
several?, the duplicates of all of which must be found? Are the
array elements integral or floating point? Is there a known minimum
and maximum bound on them? Is there a particular order that the
duplicates must be output in? Is it sufficient to output the element
and the number of duplicates, or must the locations of each be output?

If it is sufficient to output the duplicated elements and number of
duplicates, the answer is Yes, provided that enough memory is available.

--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

[christian.bau]

On May 21, 6:47 pm, ak <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

Of course. As long as you don't mind if the loop has quite a lot of
iterations.

for (k = 0; k < n*n; ++k) {
i = k / n; j = k % n;
...
}

[Richard Tobin]

In article <11*********************@y2g2000prf.googlegroups.c om>,
christian.bau <ch***********@cbau.wanadoo.co.ukwrote:

>On May 21, 6:47 pm, ak <[e-mail]:

>Is it possible to find repeated(duplicate) element in an array in
single loop ?

>Of course. As long as you don't mind if the loop has quite a lot of
iterations.

Ooh, very clever!

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[user923005]

On May 21, 10:47 am, ak <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

Yes, if you use a hash table. It's not clear if an auxilliary data
structure is allowed.
Yes, if the array is sorted. It's not clear if we know anything about
the data.

Your question is vague.

[Ramesh3839]

On May 21, 10:47 pm, ak <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

AK

Yes u can using a single pass of a loop....

but it may use an extra array space and the integer range shoould be
specified...
consider the array NUM[1...n]
consdier all numbers in the array are within the range 1...k then we
have another array A from 1...k

then the loop would be...

for(i=0;i<n;i++)
{

if(A[NUM[i]]==0)
{
A[NUM[i]]=1;
}
if(A[NUM[i]]==1)
{
printf("%d",NUM[i]);
}
}

this loop structure prints only the repeated elements in an array of
integers....

[Ramesh3839]

On May 21, 10:47 pm, ak <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

AK

Yes u can using a single pass of a loop....

but it may use an extra array space and the integer range shoould be
specified...
consider the array NUM[1...n]
consdier all numbers in the array are within the range 1...k then we
have another array A from 1...k

then the loop would be...

for(i=0;i<n;i++)
{

if(A[NUM[i]]==0)
{
A[NUM[i]]=1;
}
if(A[NUM[i]]==1)
{
printf("%d",NUM[i]);
}
}

this loop structure prints only the repeated elements in an array of
integers....

[user923005]

On May 21, 8:47 pm, Ramesh3839 <[e-mail]:

On May 21, 10:47 pm, ak <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

AK

Yes u can using a single pass of a loop....

but it may use an extra array space and the integer range shoould be
specified...
consider the array NUM[1...n]
consdier all numbers in the array are within the range 1...k then we
have another array A from 1...k

then the loop would be...

for(i=0;i<n;i++)
{

if(A[NUM[i]]==0)
{
A[NUM[i]]=1;
}
if(A[NUM[i]]==1)
{
printf("%d",NUM[i]);
}

}

this loop structure prints only the repeated elements in an array of
integers....

With unsigned integer, on a 32 bit system your array NUM has 4 billion
elements (about 16 GB in size).
I suggest that my hash table notion is a bit more practical.

IMO-YMMV.

[Mohan]

On May 22, 12:46 am, "christian.bau"
<[e-mail]:

On May 21, 6:47 pm, ak <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

is this a class room exercise?

Of course. As long as you don't mind if the loop has quite a lot of
iterations.

for (k = 0; k < n*n; ++k) {
i = k / n; j = k % n;
...

}

<OTHow about creating a binary search tree (duplicates collide)? </
OT>

Mohan

[Richard Heathfield]

Ramesh3839 said:

<snip>

>
for(i=0;i<n;i++)
{

if(A[NUM[i]]==0)
{
A[NUM[i]]=1;
}
if(A[NUM[i]]==1)
{
printf("%d",NUM[i]);
}
}

this loop structure prints only the repeated elements in an array of
integers....

Let's try it, shall we? And just for fun, let's try it on an array with
no repeats at all. So there should be no output, according to you.

#include <stdio.h>

#define n 16

int main(void)
{
int i = 0;
int A[n + 1] = { 0 };
int NUM[n] = { 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15, 16 };

for(i = 0; i < n; i++)
{

if(A[NUM[i]] == 0)
{
A[NUM[i]] = 1;
}
if(A[NUM[i]] == 1)
{
printf("%d", NUM[i]);
}
}
putchar('\n');
return 0;
}

Output:
12345678910111213141516

Oopsie!

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Tobin]

In article <11**********************@p77g2000hsh.googlegroups .com>,
user923005 <dc*****@connx.comwrote:

>Is it possible to find repeated(duplicate) element in an array in
single loop ?

>Yes, if you use a hash table.

The implementation of the hash table is likely to use another loop.

-- Richard

--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[user923005]

On May 22, 8:01 am, [e-mail] (Richard Tobin) wrote:

In article <[e-mail] .com>,

user923005 <[e-mail]:

Is it possible to find repeated(duplicate) element in an array in
single loop ?

Yes, if you use a hash table.

The implementation of the hash table is likely to use another loop.

Does it count if we unroll it?

[CBFalconer]

Richard Tobin wrote:

user923005 <dc*****@connx.comwrote:

>>Is it possible to find repeated(duplicate) element in an array in
single loop ?

>Yes, if you use a hash table.

The implementation of the hash table is likely to use another loop.

Not so. For a std C implementation that expects insertion,
deletion, search to all be O(1) see:

<http://cbfalconer.home.att.net/download/hashlib.zip>

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

[Richard Harter]

On 22 May 2007 14:20:22 -0700, user923005 <dc*****@connx.comwrote:

>On May 22, 8:01 am, [e-mail] (Richard Tobin) wrote:

>In article <[e-mail] .com>,

user923005 <[e-mail]:

>Is it possible to find repeated(duplicate) element in an array in
single loop ?
Yes, if you use a hash table.

The implementation of the hash table is likely to use another loop.

Does it count if we unroll it?

And you are going to do this, how?

[Richard Tobin]

In article <46***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:

>>Yes, if you use a hash table.

>The implementation of the hash table is likely to use another loop.

>Not so. For a std C implementation that expects insertion,
deletion, search to all be O(1) see:

Being O(1) has little to do with whether there's a loop. So long as
the expected number of items it compares against doesn't depend on N,
it's still O(1). I assume you mean that your hash table tries to
ensure a fixed maximum number of comparisons - perhaps one - in which
case it will have to adjust the table periodically, which is again
likely to use a loop. I'd be very surprised to see a hash table
implementation that never uses a loop.

Of course, you can always satisfy the letter of the law by using
recursion as a substitute for looping,

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.