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

^{2})

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"

Space Complexity :O(1)

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

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.