Shrivatsan
Shrivatsan

Reputation: 105

How to find series of unique numbers in an array by discarding repetitive elements

I am able to find out the unique elements from a sorted array in my given piece of code. I need a solution for finding the unique elements by avoiding repetitive numbers i.e. from a Non sorted array of the format {0,1,1,2,3,4,4,1,3,5,9,12,12,13,14}.

C Program:

#include<stdio.h>
#define ARRAY_SIZE  15
int main()
{
  int arr[ARRAY_SIZE]={0,1,1,2,3,4,4,1,3,5,9,12,12,13,14};
  int i=0,j=0,t;
  printf("\nThe Array elements are : ");
  for(i=0; i<ARRAY_SIZE;i++)
  printf("%d ",arr[i]);
  for (j=0 ; j<(ARRAY_SIZE-1) ; j++)
      {
         for (i=0 ; i<(ARRAY_SIZE-1) ; i++)
             {
                if (arr[i+1] < arr[i])
                   {
                      t = arr[i];
                      arr[i] = arr[i + 1];
                      arr[i + 1] = t;
             }
      }
}
  printf("\n\nunique elements are : ");
  printf("%d ",arr[0]);
  for(i=1;i<ARRAY_SIZE;i++)
    {
        /* check current number and prev number if they are different that mean we met    
        another unique element */

        if(arr[i-1]^arr[i])
        /*a^b = zero only if two numbers are different*/                                        
         {        
           printf("%d ",arr[i]);
         }
    }
return 0;
}

Upvotes: 0

Views: 133

Answers (3)

/*
To avoid too many iterations, after finding the duplicates  break the inner loop 
*/
#include <stdio.h>
#include  <stdlib.h>
int main()
{
   int a[] = {50,1, 34, 1, 3, 11, 75, 3, 4, 9, 11, 4, 9, 3, 34, 100,0,100};
   int arr[sizeof(a)/ sizeof(a[0])] = { 0 };

   int i = 0, j = 0;

   for(i = 0; i < (sizeof(a) / sizeof(a[0])); i++)
   {
       for(j = i+1; j < (sizeof(a)/ sizeof(a[0])); j++)
       {
           if(a[i] == a[j])
           {
               ++arr[i];
               ++arr[j];
               break; // used to avoid too many iterations.
           }
       }
       if(arr[i] == 0) //must have unique number
       {
           printf ("The unique numbers = %d\n", a[i]);
       }
   }
   return 0;  
}

Upvotes: 1

ldgabbay
ldgabbay

Reputation: 1183

This may be overkill, but:

#include <stdio.h>
#include <stdlib.h>

int array_contains(const int* arr, size_t len, int elem) {
    int i;
    for (i=0; i!=len; ++i)
        if (arr[i]==elem)
            return 1;
    return 0;
}

void print_uniques(const int* arr, size_t len) {
    size_t uniques_len = 0;
    int uniques_arr[len];
    int i;
    for (i=0; i!=len; ++i)
        if (!array_contains(uniques_arr, uniques_len, arr[i]))
            uniques_arr[uniques_len++] = arr[i];
    for (i=0; i!=uniques_len; ++i)
        printf("%d ", uniques_arr[i]);
    printf("\n");
}

#define ARRAY_SIZE  15
int main()
{
    int arr[ARRAY_SIZE]={0,1,1,2,3,4,4,1,3,5,9,12,12,13,14};
    print_uniques(arr, ARRAY_SIZE);
    return 0;
}

Yes, this is O(N^2). You could improve this by using some sort of hashset rather than maintaining an unordered list. I would also check out hsearch.

Upvotes: 1

Igor
Igor

Reputation: 27258

If there are no performance requirements, you can do:

  1. Sort the array.
  2. Execute the code that you posted.

Upvotes: 0

Related Questions