duplicates in array

[ak]

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

AK

 

[Walter Roberson]

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.

 

[christian.bau]

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]

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

Ooh, very clever!

-- Richard

 

[user923005]

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]

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]==0)
{
A[NUM]=1;
}
if(A[NUM]==1)
{
printf("%d",NUM);
}
}

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

 

[Ramesh3839]

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]==0)
{
A[NUM]=1;
}
if(A[NUM]==1)
{
printf("%d",NUM);
}
}

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

 

[user923005]

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]==0)
{
A[NUM]=1;
}
if(A[NUM]==1)
{
printf("%d",NUM);
}

}

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]

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

}

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

Mohan

 

[Richard Heathfield]

Ramesh3839 said:

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

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

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] == 0)
{
A[NUM] = 1;
}
if(A[NUM] == 1)
{
printf("%d", NUM);
}
}
putchar('\n');
return 0;
}

Output:
12345678910111213141516

Oopsie!

 

[Richard Tobin]

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

[/QUOTE]

Yes, if you use a hash table.

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

-- Richard

 

[user923005]

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

Does it count if we unroll it?

 

[Richard Harter]

Does it count if we unroll it?

And you are going to do this, how?

 

[Richard Tobin]

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

[/QUOTE]

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