Print All Distinct Elements of the Array

Problem Statement

We have an array of containing N integers which may be positive or negative. We have to print all distinct elements of the array. In other words, we can say that if a number occurs more than one time then we print only that number once.

Example

Input

8

2 3 1 2 3 5 4 -5

Output

2 3 1 5 4 -5

We can solve this question in so many ways and some of those approaches are used below. Please read patiently because every approach leads your knowledge.

 Approach 1 for Print All Distinct Elements of the Array

We can store the frequency of every element and print every number only once.

Algorithm

1. Simply Hash all the values and increase their count from 0 to the number of times they occur.

2. While printing we check if the count of that key is more than 0 and if yes we print it once.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  unordered_map<int,int> m;
  for(int i=0;i<n;i++)
  {
      m[a[i]]++;
  }
  unordered_map<int,int> :: iterator i;
  for(i=m.begin();i!=m.end();i++)
  {
    cout<<i->first<<" ";  
  }
}

Java Program

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        HashMap <Integer,Integer> m = new HashMap<Integer, Integer>() {}; // create a map with key as the array element and value as if it is present or not
        for(int i=0;i<n;i++)
        {
            int x = m.get(a[i])==null? 1: m.get(a[i])+1;
            m.put(a[i],x);
        }
        for(Map.Entry u : m.entrySet()) 
        {
            int key = (int) u.getKey();
            System.out.println(key+" ");
        }
    }
}

8
2 1 -2 3 4 3 2 1

4 3 -2 2 1

Complexity Analysis for Print All Distinct Elements of the Array

Time Complexity: O(N) where N is the number of elements present in the array.

Space Complexity: O(N) because we use map to store the frequency of each elements.

Approach 2 for Print All Distinct Elements of the Array

When we use the SET data structure which containing elements in sorted order and each element present only once in the set. Below is the implementation using SET.

Algorithm

1. Use the SET data structure that stores unique keys and in a sorted manner.

2. Simply add all the elements and traverse the set using an iterator.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  set<int> S; // Set data structure stores unique element and  too sorted 
  
  for(int i=0;i<n;i++)
    S.insert(arr[i]);
    
  set<int> :: iterator it; //just traverse the set simply
  for(it = S.begin(); it != S.end(); it++)
    cout << *it << " ";
    
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Set<Integer> hs = new HashSet<Integer>();
        // Elements are added using add() method
        for(int i=0;i<n;i++)
        {
            hs.add(a[i]);
        }
        // Iterating though the Set
        for (Integer value : hs)
            System.out.print(value + " ");
        System.out.println();
    }
}

8
2 1 -2 3 4 3 2 1

-2 1 2 3 4

Approach 3 for Print All Distinct Elements of the Array

Using sorting we can also print the distinct numbers.

Algorithm

1. Sort the array.

2. Traverse the array and skip similar adjacent elements.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  sort(arr,arr+n); // sort the array so that similar elements will occur adjacent
  
  for(int i=0;i<n;)
  {
    cout << arr[i++] << " ";
    while(arr[i] == arr[i-1] and i < n)
      i++;
  }
    
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a); // sort the array so that similar elements will occur adjacent  
        for(int i=0;i<n;)
        {
          System.out.print(a[i++]+ " ");
          while(i<n && a[i] == a[i-1])
            i++;
        }
        System.out.println();
    }
}

8
3 2 1 5 3 2 1 -5

-5 1 2 3 5