duplicates in array

[ak]

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

AK

[Walter Roberson]

In article <11************ ********@u36g20 00prd.googlegro ups.com>,
ak <aj**********@g mail.comwrote:

>Is it possible to find repeated(duplic ate) 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 <ajinkya.c...@g mail.comwrote:

Is it possible to find repeated(duplic ate) 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************ *********@y2g20 00prf.googlegro ups.com>,
christian.bau <ch***********@ cbau.wanadoo.co .ukwrote:

>On May 21, 6:47 pm, ak <ajinkya.c...@g mail.comwrote:

>Is it possible to find repeated(duplic ate) 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
--
"Considerat ion 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 <ajinkya.c...@g mail.comwrote:

Is it possible to find repeated(duplic ate) 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 <ajinkya.c...@g mail.comwrote:

Is it possible to find repeated(duplic ate) 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 <ajinkya.c...@g mail.comwrote:

Is it possible to find repeated(duplic ate) 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 <prames...@gmai l.comwrote:

On May 21, 10:47 pm, ak <ajinkya.c...@g mail.comwrote:

Is it possible to find repeated(duplic ate) 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"
<christian....@ cbau.wanadoo.co .ukwrote:

On May 21, 6:47 pm, ak <ajinkya.c...@g mail.comwrote:

Is it possible to find repeated(duplic ate) 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:
123456789101112 13141516

Oopsie!

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