• C

Duplicate Element

How to remove duplicate elements in C?

int main()
{

   int a[] = { 10,20,30,40,50,10,20,50};  // how to remove duplicates from this array
 
  return (0);
}


gauravflameAsked:
Who is Participating?
 
ozoConnect With a Mentor Commented:
// this is O(n + max element)
// with a little more work, it could be made O(n), assuming O(max element) fits in memory
// if it does not fit, you could still do it in O(n) expected time, O(n log n) worst case

#include <stdlib.h>
#define len(a) (sizeof(a)/sizeof(*a))
int n=0;
unsigned int m=0;
 for(int i=0; i < len(a); i++){ if( a[i] > m ){ m = a[i]; } }
 char *s=(char *)calloc(m,1);
 for(int i =0; i < len(a); i++){
  int j=0;
  if( !s[a[i]] ){
    a[n++]=a[i];
  }
  s[a[i]]=1;
}
0
 
ozoCommented:
Are all the elements small integers?
Would you me satisfied with an O(n*n) method?
0
 
gauravflameAuthor Commented:
can you provide me both solution in O(n*n) and in O(nlogn)
0
Worried about phishing attacks?

90% of attacks start with a phish. It’s critical that IT admins and MSSPs have the right security in place to protect their end users from these phishing attacks. Check out our latest feature brief for tips and tricks to keep your employees off a hackers line!

 
ozoCommented:
O(n*n) for each item, scan the array to see if the item has been seen before
O(n*log(n)) sort the array (but do you want to preserver order?)
O(n) or O(max item) time O(max item) space:  keep an array indexed by item to record seen items
0
 
gauravflameAuthor Commented:
O(n) solution will be great.
How to implement in this form?
0
 
gauravflameAuthor Commented:
I know how to do in O(n*n) times .. .. still this is not a best way to do
still I have problem in this way , what I shat I do when I will get duplicate element
int a[] = { 10,20,30,40,50,10,20,50};  
for(int i =0; i < 5; i++)
{
   for(int j =0; j < 5; j++)
   {
            if(a[i] == a[j])
                {  
                        printf("Dupicate Found");
                        // How to remove the element from the array  ..so that array don't contain
                        // empty element
               }
  }
}



0
 
Infinity08Commented:
>> // How to remove the element from the array

If increased storage is no concern, then you might consider a linked list instead of an array. The problem with removing an element from an array is that you have to shift all elements after that. A linked list doesn't have that problem.

You could also, instead of removing the element from the array, just set it to an invalid value (eg. -1), and ignore it in the further operations of the array. Depending of the application, and how many elements you are gonna remove, that might be a valid alternative.


0
 
ozoCommented:
int n=0;
for(int i =0; i < 5; i++)
{
  int j=0;
  for( j =0; j < i; j++)
    {
      if(a[i] == a[j])
        {
          printf("Dupicate Found");
          // How to remove the element from the array  ..so that array don't contain
          // empty element
          break;
        }
    }
  if( j==i ){
    a[n++]=a[i];
  }
}

///the first n elements of the array are now unique
0
 
gauravflameAuthor Commented:
The above solution is O(n*n) times  .Can you provide me the solution in the O(n) time

0
 
abithConnect With a Mentor Commented:
O(n) times :)

this will run only if array contains less than 70

      int repeat[]= {10,10,50,20,20,30,40,50,10,20,50};
      int start = 0;
      int pos =0;
      char flag = 0;
      int i ;
      for (i=0; i < sizeof(repeat)/ sizeof(*repeat); i++)
      {
            int c = repeat[i] / 10 ;
            if(!( flag & (1 << (c+1)) ))
            {
                  repeat[start++] = repeat[pos];
                  flag |= (1 << (c+1));
            }            
            pos++;
      }      

      for (i=0;i<start;i++)
            cout << repeat[i] << endl;
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.