C Program to Print Distinct Elements of Array

  • Write a program to print all distinct elements of an array.
  • How to find all distinct elements of an array in linear time complexity.

Given an integer array of size N we have to print all distinct elements of input Array. Input array may contain duplicate elements we have to print one element only once.
For Example :

Input Array : 4, 6, 5, 3, 4, 5, 2, 8, 7, 0
Distinct Elements : 0 2 3 4 5 6 7 8

Let inputArray be an integer array of size N.

Brute Force
Algorithm to find unique elements of array
  • In this algorithm we will search for duplicates of every array element using two for loop.
  • Outer for loop will fix one array element(let's say K) and inner for loop will search for duplicate of K in remaining array.
  • If duplicate of K is found then continue else K is a distinct element and print it.
Time Complexity : O(n2)
Space Complexity :O(1)

C program to find unique elements of array by searching duplicate of every element

#include <stdio.h>

/* Prints distinct elements of an array */
void printDistinctElements(int *array, int size){
    int i, j;
    
    for(i = 0; i < size; i++) {       
        for(j = i+1; j < size; j++) {
            if(array[i] == array[j]){
               /* Duplicate element found */
               break;
            }
        }
         /* If j is equal to size, it means we traversed whole 
  array and didn't found a duplicate of array[i] */
        if(j == size)
           printf("%d ", array[i]);
    }
}

int main(){
    int array[10] = {4, 6, 5, 3, 4, 5, 2, 8, 7, 0}; 
    int i;
    
    printDistinctElements(array, 10);

    return 0;
}
Output
6 3 4 5 2 8 7 0
By Sorting Input Array
The main idea behind this algorithm is that "In a sorted array, all duplicate elements group together in adjacent positions"
  • Sort inputArray.
  • Traverse input array from index 0 to N-1. Check if current element is same as next element. If true then skip current element otherwise print it.
Time Complexity : O(nLogn)
Space Complexity :O(1)

C program to find distinct elements by sorting input array

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

/* Comparator function for qsort */
int compare(const void *a, const void *b) {
   return ( *(int*)a - *(int*)b );
}

/* Prints distinct elements of an array */
void printDistinctElements(int *array, int size){
    int i, j;
    /* Sort input array */
    qsort(array, size, sizeof(int), compare);
    /* After sorting all duplicate elements will 
    be iin adjacent positions */
    for(i=0; i<size; i++) {
     if(i == size-1) {
         /* Boundary condition handling */
            printf("%d ", array[i]);
        } else if (array[i] != array[i+1]) {
            printf("%d ", array[i]);
        }
    }
}

int main(){
    int array[10] = {4, 6, 5, 3, 4, 5, 2, 8, 7, 0}; 
    int i;
    
    printDistinctElements(array, 10);

    return 0;
}
Output
0 2 3 4 5 6 7 8
By Using Hash Table
We can use a hash table to store count of all elements traversed till now. Using a hash table we can find solve this problem in O(n) time complexity but it requires extra space for hash table.
  • Initialize a hash table.
  • Traverse inputArray and check whether current element is present in hash table or not.
  • If not present in hash table then print it and add it in hash table.
  • If current element is present in hash table then skit it and continue.
Time Complexity : O(n)
Posted by
Labels: ,