C Program To Find Number of Distinct Elements in an Array

In this tutorial, we will see how to find the total number of distinct elements in the given unsorted array. But before moving forward if you are not familiar with the concept of the array in C, then do check the article on Arrays in C.

Below is the pictorial representation of the same.

Input : Enter the array elements: 5 8 4 5 9 1 5

Output: Total number of distinct elements: 5

There are 5 distinct elements here 5 4 8 9 1

Program 1: Find the Total Number of Distinct Elements in an Array

This is the simplest solution to find the number of distinct elements in an array. Here, for loops are used to check whether that element has appeared before or not. If yes, then increment the count of the distinct elements.

In this method, we will use two for loops to find the number of distinct elements. Here, the first for loop will fix the one array and the inner for loop will look for duplicate elements in the remaining array. The time complexity for this solution is O(n2).

Algorithm

1. Start
2. Declare an array.
3. Initialize the array.
4. Call a function to count the distinct elements.
5. Declare a count variable and initialize it to 1.
6. Declare two for loops.
7. Use the first for loop to fix one array element.
8. Use the second loop to look for duplicate elements in the remaining elements.
9. Increment the count variable if elements previously not counted.
10. Return the count variable.
11. End.

Below is the code for the same.

#include <stdio.h>
int countDistinct(int a[], int n)      //Function Definition
{
   int i, j, count = 1;
   //Traverse the array
   for (i = 1; i < n; i++)      //hold an array element
   {
      for (j = 0; j < i; j++)   
      {
         if (a[i] == a[j])    //Check for duplicate elements
         {
            break;             //If duplicate elements found then break
         }
      }
      if (i == j)
      {
         count++;     //increment the number of distinct elements
      }
   }
   return count;      //Return the number of distinct elements
}
int main()
{
    int n;       //Declare array size
    printf("Enter the number of elements \n");
    scanf("%d",&n);    //Initialize the array size

    int a[n];   //Array Declaration
    printf("Enter the array elements : ");
    for (int i=0;i<n;i++)
    scanf("%d",&a[i]);   //Initialize the array elements

    int c= countDistinct(a,n);       //Function Call
    printf("The number of distinct elements are %d",c);   //Print the number of distinct elements
    return 0;
}

Enter the number of elements 5
Enter the array elements: 2 5 4 2 4
The number of distinct elements are 3

Program 2: Find the Total Number of Distinct Elements in an Array

The main concept behind this algorithm is that "In a sorted array, all duplicate elements group together in adjacent positions". Firstly sort the given array and then traverse the array from index 0 to N-1 where N is a natural number. Then, we will check if the current element is the same as the next element. If same, then we will skip the element else increment the count variable.

Algorithm

1. Start
2. Declare an array.
3. Initialize the array.
4. Declare a temporary variable.
5. Sort the elements.
6. After sorting duplicate elements are in adjacent positions.
7. Traverse through the elements.
8. Move the index if a duplicate element is found.
9. Increment the count
10. Print the number of distinct elements.
11. End

Below is the code for the same.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number of elements \n");
    scanf("%d",&n);
    int a[n];    //Declare an array
    printf("Enter the array elements : ");
    for (int i=0;i<n;i++)     //Initialize the array
    scanf("%d",&a[i]);
    for (int i = 0; i < n; i++) {   //Sort the array
        int temp;
        for (int j = i+1; j < n; j++) 
        {     
           if(a[i] > a[j]) {    
               temp = a[i];    
               a[i] = a[j];    
               a[j] = temp;    
           }     
        }     
    }    
    //Print the sorted array
    printf("Elements after sorting....");
    for (int i=0;i<n;i++)
    printf("%d ",a[i]);
    printf("\n");      
    int count = 0;
    for (int i = 0; i < n; i++)  //Traverse the array
    {
      // Moving the index when duplicate is found
      while (i < n - 1 && a[i] == a[i + 1])
      {
         i++;
      }
      count++;    //Increment count to take a note of distinct element
    }
    printf("The number of distinct elements are %d",count);   //Prints the number of distinct elements
    return 0;
}

Enter the number of elements 5
Enter the array elements: 4 6 4 5 7
Elements after sorting....4 4 5 6 7
The number of distinct elements are 4