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

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

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

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 

Your algorithm might take much longer time when the max value in the array is very big. Memorising which element was counted already seems to be better in order to reduce computational complexity.

My code below memorises which element was counted and skips counting an element if it was counted already. I use a flag array to memorise counted element.

#include <stdlib.h>

int num_distinct(int a[], int n) {
    int* flag;
    int all_counted = 0;
    int i, cur, count = 0;
    int cur_flag;

    flag = (int*)malloc(n);
    for (i = 0; i < n; i++) flag[i] = 0;

    while (all_counted == 0) {
        cur_flag = 0;
        for (i = count; i < n; i++) {
            if (cur_flag == 0 && flag[i] == 0) {
                flag[i] = 1;
                cur_flag = 1;
                cur = a[i];
                count++;
            } else if (cur_flag == 1 && cur == a[i]) {
                flag[i] = 1;
            }
        }
        if (cur_flag == 0) all_counted = 1;
    }
    free(flag);
    return count;
}