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