Home »
Data Structure »
Array Data Structure
Print all distinct elements of a given integer array
Learn how to print all distinct elements of a given integer array using C++ programs?
Submitted by Vikneshwar GK, on January 16, 2022
An array can have elements that repeat itself, i.e., contain duplicates. The task at hand is to print all the elements of the array only without repeating itself.
Example:
Input:
test1[] = {4, 0, 1, 8, 3, 4, 7, 0, 1}
Output:
4 0 1 8 3 7
Explanation:
Elements 0, 1, and 4 are present twice in the array.
Therefore, they are printed only once.
The rest of the elements are printed normally.
Input:
test1[] = {5, 4, 1, 2, 0}
Output:
5 4 1 2 0
Explanation:
All the elements are present only once.
Therefore, they are all printed.
Solution 1: Using Nested Loop
This method of approach involves using two loops where the outer loop points to an element and the inner loop check whether that element is present from the beginning of the array till the current element index. If it is not present earlier, then the element is printed, else it is skipped.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
void displayUnique(int array[], int size)
{
// Outer loop
// Traverse entire array
for (int i = 0; i < size; i++) {
int j;
// Inner loop
// Traverse from 0 to i
for (j = 0; j < i; j++)
// if present earlier, then break
if (array[i] == array[j])
break;
// If it is not present earlier
// then print the element
if (i == j)
cout << array[i] << " ";
}
}
// Driver function
int main()
{
int array[100], size;
cout << "Enter Number of elements: ";
cin >> size;
for (int i = 0; i < size; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
displayUnique(array, size);
return 0;
}
Output:
Enter Number of elements: 7
Enter element 1:1
Enter element 2:7
Enter element 3:5
Enter element 4:4
Enter element 5:1
Enter element 6:7
Enter element 7:1
1 7 5 4
Time Complexity: Since it is a nested loop traversal, the time complexity is O(n2).
Solution 2: Using Sort
In this approach, sort the array using an O(n log(n)) algorithm. After sorting, all the elements that are present more than once will be placed next to each other. Now we can easily compare the adjacent elements and print the elements only once. One drawback to this approach apart from time complexity is that the elements will not be printed in the given order, rather it will be sorted and printed.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
void displayUnique(int array[], int size)
{
// Sort the array
sort(array, array + size);
// Interate through the array
for (int i = 0; i < size; i++) {
// Increment to index if duplicates are present
while (i < size - 1 && array[i] == array[i + 1])
i++;
// print the element
cout << array[i] << " ";
}
}
// Driver program to test above function
int main()
{
int array[100], size;
cout << "Enter Number of elements: ";
cin >> size;
for (int i = 0; i < size; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
displayUnique(array, size);
return 0;
}
Output:
Enter Number of elements: 7
Enter element 1:4
Enter element 2:1
Enter element 3:1
Enter element 4:2
Enter element 5:3
Enter element 6:4
Enter element 7:2
1 2 3 4
Time Complexity: O(nlog(n))
It is the time complexity of the sorting algorithm as the printing of unique elements take only negligible time.
Solution 3: Using Hash function
It is a simple yet very efficient approach. We will traverse through the array and check whether the element is present in the hash table. If not present, then put it in and print the element. If present, simply skip it and move to the next element.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
void displayUnique(int array[], int size)
{
// declare an empty hashset
unordered_set<int> hash_table;
// Traverse the input array
for (int i = 0; i < size; i++) {
// if the current element is
// not present is hash_table
// then print it and put it in the table
if (hash_table.find(array[i]) == hash_table.end()) {
hash_table.insert(array[i]);
cout << array[i] << " ";
}
}
}
// Main function
int main()
{
int array[100], size;
cout << "Enter Number of elements: ";
cin >> size;
for (int i = 0; i < size; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
displayUnique(array, size);
return 0;
}
Output:
Enter Number of elements: 8
Enter element 1:1
Enter element 2:3
Enter element 3:1
Enter element 4:5
Enter element 5:4
Enter element 6:3
Enter element 7:4
Enter element 8:1
1 3 5 4
Time Complexity: O(n)