Print All Distinct Elements of the Array

Difficulty Level Easy
Frequently asked in Adobe Factset MAQ o9 solutions TCS
Array Hashing HashMapViews 2291

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 << " ";
    
}

Java Program

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

Complexity Analysis for Print All Distinct Elements of the Array

Time Complexity: O(NlogN) because insertion in SET takes logN time. So, here is the size of the array is N that’s why the time complexity in this nlogn.

Space Complexity: O(N) because we use SET for storing the elements. And the maximum size possible for SET is N.

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++;
  }
    
}

 Java Program

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

Complexity Analysis

Time Complexity: O(NlogN) here we use the sort function which has nlogn time complexity.

Space Complexity: O(1) because we don’t use any auxiliary space here.

References

Translate »