A program that counts unique elements in an un-ordered array

Question

int num_distinct(int a[], int n)
{
  int i, k, j, count=0;
  int max = a[0];

  for (i = 1; i < n; i++) {
    if (max < a[i]) {
      max = a[i];
    }
  }
  for (k = 0; k < n; ++k) {
    for (j = 0; j < n; ++j) {
      if (a[j] == max) {
        ++count;
        --max;
        break;
      }
    }
  }
  return (count);
}

What i tried to do is find the max in the array and compare that to the rest of the elements in the array. It works, but when the array skips a number i.e. (1,2,2,5,6,7,8) <-- it skipped 3 and 4. My code will only count 8,7,6,5 which returns 4 unique numbers.

Solution 1

Sometimes simplicity rules.

int unique_elements(int arr, int len)
{
     if (len <= 0) return 0;
     int unique = 1;

     for (int outer = 1; outer < len; ++outer)
     {
        int is_unique = 1;
        for (int inner = 0; is_unique && inner < outer; ++inner)
        {  
             if (arr[inner] == arr[outer]) is_unique = 0;
        }
        if (is_unique) ++unique;
     }
     return unique;
}

The logic is that the outer loop picks the value to be tested, and the inner loop checks it against all preceding values. If the value is found, it is not unique, so the count is incremented.

The advantage of this is no usage of temporary storage (whether a VLA, or use of malloc()). It also does not try to work out the max, or count number of repetitions, or anything like that.

The worst case execution time is if all values are unique (i.e. no repeated values in the array).

Solution 2

just to let you know, @kcDod's algorithm is flawed. It won't count elements like this: 1, 2, 3, 4, 9000, 4, 2 try and you will see:

the below code will count regardless of the elements and requires much less power, you don't count unique elements by incrementing or decrementing the maximum in an array, I don't know where you got that idea.

int unique_elements(int arr[], int len) {

    int counted[len], j, n, count, flag;

    counted[0] = arr[0]; 

    count = 1;/*one element is counted*/

        for(j=0; j <= len-1; ++j) {
        flag = 1;;
        /*the counted array will always have 'count' elements*/
        for(n=0; n < count; ++n) {
            if(arr[j] == counted[n]) {
                flag = 0;
            }
        }
        if(flag == 1) {
            ++count;
            counted[count-1] = arr[j];
        }
    }
    return count;
}


int main(void) {
    int arr[13] = {1, 2, 2, 123121, 123121, 3, 5, 6 , 7, 7, 14, 2, 16};
    printf("%d", unique_elements(arr, 13));
    return 0;
}

Solution 3

This shall work .. Replace second for loop set with this.

int flag = 0; // We need to flag that we found a max in the iteration. So don't count again

for (k = 0; k < n;){
     for (j = 0; j < n; ++j) {         
          if (a[j] == max){
             if (flag==0){
                 ++count; // We count an occurrence only once 
                 flag = 1;
              }
             k++; // We should decrease the search when we found an element from original array
          }
      }
    // Reset parameters
    --max;
    flag = 0;
}

A working example :

#include <stdio.h>

int main()
{
    int a[7] = { 7,2,2,4,5,6,7};
    int n = 7; // Number of elements in the array 

    int max=0;
    int i, k, j=0;

    for (i = 1; i < n; i++)
    {
        if (max < a[i])
         {
            max = a[i];
        }
    }

    int count=0;
    int flag = 0;

    for (k = 0; k < n;)
    {
        for (j = 0; j < n; ++j)
        {
            if (a[j] == max)
            {
                if (flag==0)
                {
                    ++count;
                    flag = 1;
                }
             k++;
         }
        }
        --max;
         flag = 0;
    }

    printf("Unique elements : %d\n",count);
}

Output :

Unique elements : 5 

Comments

[LearningCODE]

Thanks, but this just counts all elements not unique elements.

[theadnangondal]

int arr[] = {1,2,2,5,6,7,8,3,9,1}; int dis_num = num_distinct(arr,10); the output is 8 instead of 7 ..

[theadnangondal]

shouldn't it be 6 ?? because 2 and 1 are not unique

[theadnangondal]

occurences of 2 and 1 are more then 1 times

[Kavindu Dodanduwa]

@headnangondal - from OP owners comment "for example a[1,4,2,6,6,7,8,5,5,4], this a aray would have 7 unique elements".

[LearningCODE]

It worked perfectly thank you so much^.^ I can't believe I missed that I have been coding all day, must of gotten tunnel vision.. Thanks again!!!!

[Kavindu Dodanduwa]

@user3539833 Problem was with your algorithm. next time before you code write down it on a paper and check.. Mark answer as 'correct' if you accept it..

[chux - Reinstate Monica]

flag = (int*)malloc(n); too small an allocation. Use flag = malloc(sizeof *flag * n);.

[chux - Reinstate Monica]

int arr makes more sense as int *arr or even better const int *arr.