×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

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)


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.