Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Example for Sample Input and Output
2.
Approach 1: Brute Force
2.1.
Algorithm
2.2.
C++ Implementation
2.3.
Java Implementation
2.4.
Python Implementation
2.5.
Complexity Analysis
3.
Approach 2: Using Hashing
3.1.
Algorithm
3.2.
C++ Implementation
3.3.
Java Implementation
3.4.
Python Implementation
3.5.
Complexity
4.
Frequently Asked Questions
4.1.
How do I print the number of distinct elements in an аrrаy?
4.2.
Whаt аre distinct elements?
4.3.
Whаt аre the properties of the hаsh tаble?
4.4.
Whаt аre the three bаsic operаtions on а hаsh tаble?
4.5.
Why аre h��sh tаbles fаst?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Print All Distinct Elements Of A Given Integer Array

Author Aditya kumar
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

In the blog, we will look at the problem statement to print all distinct elements of a given integer array. The output for this problem should print each entry only once because the specified array can include duplicates. The array being used is not ordered(or sorted).

Distinct elements

Example for Sample Input and Output

Sample Input Sample Output
Arr[]={12,3,31,12,32,32} 12 3 31 32
Arr[]={7,3,5,1,7,5,34} 7 3 5 1 34

 

Approach 1: Brute Force

Check each element to see if there is another element that is present that has the same value as the current element but a lower index. Print the current element if there isn't one; otherwise, skip it if it is absent.

Algorithm

  1. Run a loop from ‘0’ to ‘n-1’ for integer ‘i’.
    1. Run a for ‘j; loop from ‘0’ to ‘i’.
      1. Print Arr[i] if j==i.
      2. Break out of this loop if Arr[i] === Arr[j].
    2. Return.

C++ Implementation

/*
	Print all distinct elements of a given integer array
*/

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cout<<"Input the array size"<<endl;
    cin>>n;
    vector<int> Arr(n);
    cout<<"Input the integers in the array:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>Arr[i];
    }
    cout<<"The distinct elements of the array are: ";
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==i)
            {
                cout<<Arr[j]<<" ";
            }
            if(Arr[i]==Arr[j])
            {
                break;
            }
        }
    }
    return 0;
}

Output

C++ Output

Java Implementation

/*
	Print all distinct elements of a given integer array
*/

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        System.out.println("Input the array size");
        int n = sc.nextInt();
        int[] Arr = new int[n];
        System.out.println("Input the integers in the array:");
        for(int i=0;i<n;i++)
        {
            Arr[i] = sc.nextInt();;
        }
         System.out.print("The distinct elements of the array are: "); 
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j==i)
                {
                    System.out.print(Arr[i]+" ");
                }
                if(Arr[i]==Arr[j])
                {
                    break;
                }
            }
        }
  }
}

Output

Java Output

Python Implementation

#Print all distinct elements of a given integer array

def printAllDistinctEle(Arr, n):
    print("The distinct elements of the array are:",end=" ")
    for i in range(0, n):
        d = 0
        for j in range(0, i):
            if (Arr[i] == Arr[j]):
                d = 1
                break
        if (d == 0):
            print(Arr[i],end=" ")
     
Arr = []
n = int(input("Input the array size\n"))
print("Input the integers in the array:")
for i in range(0, n):
    ele = int(input())
    Arr.append(ele)
printAllDistinctEle(Arr, n)

Output

Python Output

Complexity Analysis

Time Complexity

Each of our two nested loops is of size ‘N’, the time complexity is therefore O(N2).

Space Complexity

The space complexity is O(1) because we haven't used any additional space.

Check out this array problem - Merge 2 Sorted Arrays

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2: Using Hashing

The elements we have already printed will be kept in a hash table that we maintain. Therefore, as we iterate the array, if we discover an element that is missing from the hash table, we will print it out and add it to the hash table; otherwise, we will skip over it.

Algorithm

  1. Initialize a hash table.
  2. Run a loop from ‘0’ to ‘n-1’ for ‘i’:
    1. Print Arr[i] and place it into the hash table if it's not already there.
    2. Skip it if Arr[i] does not exist in the hash table.
  3. Return.

Let us take an example to understand the Working of this algorithm.

For example, the input array is Arr[]={12,3,1,12,3}

Our input array is represented by the table on the left, where the purple color designates the current index.

The hash table is the one on the right.

Step 1

At first the hash table is empty. So, 12 is not present in the hash table; therefore  we will print it and insert it in the hash table.

Hash table

Step 2

Now, the next element in the array, i.e., 3 is not present in the hash table so we will print it and insert it in the hash table.

Hash table

Step 3

The next element 1 is not present in the hash table so we will print it and insert it in the hash table.

Hash table

Step 4

The 4th element, i.e., 12 is already present in the hash table so we will skip it.

Hash table

Step 5

The last element in our array,i.e., 3 is already present in the hash table so we will skip it.

Hash table

So the final output is: 12 3 1

C++ Implementation

/*
	Print all distinct elements of a given integer array
*/

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cout<<"Input the array size"<<endl;
    cin>>n;
    vector<int> Arr(n);
    cout<<"Input the integers in the array:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>Arr[i];
    }
    unordered_set<int> hashtable;
    cout<<"The distinct elements of the array are: ";
    for(int i=0;i<n;i++)
    {
        if(hashtable.count(Arr[i])==0)  //hashtable. If x is present in the hashtable count(x) yields 1, else it returns 0.
        {
            hashtable.insert(Arr[i]);
            cout<<Arr[i]<<" ";
        }
    }
    return 0;
}

Output

C++ output

Java Implementation

/*
	Print all distinct elements of a given integer array
*/

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        System.out.println("Input the array size");
        int n = sc.nextInt();
        int[] Arr = new int[n];
        System.out.println("Input the integers in the array:");
        for(int i=0;i<n;i++)
        {
            Arr[i] = sc.nextInt();;
        }
        Set<Integer> hashtable = new HashSet<Integer>(); 
        System.out.print("The distinct elements of the array are: ");
        for(int i=0;i<n;i++)
        {
            if(!hashtable.contains(Arr[i]))  
            {
                hashtable.add(Arr[i]);
                System.out.print(Arr[i]+" ");
            }
        }
  }
}

Output

Java Output

Python Implementation

# Print all distinct elements of a given integer array

def printAllDistinctEle(Arr, n):
    print("The distinct elements of the array are:",end=" ")
    hashset = dict();
    for i in range(n):
        if (Arr[i] not in hashset.keys()):
            hashset[Arr[i]] = Arr[i];
            print(Arr[i], end = " ");
     
Arr = []
n = int(input("Input the array size\n"))
print("Input the integers in the array:")
for i in range(0, n):
    ele = int(input())
    Arr.append(ele)
printAllDistinctEle(Arr, n)

Output

Python Output

Complexity

Time Complexity

Since we only iterate the array once and the insert function in the unordered set has an O(1) time complexity, the overall time complexity is O(N).

Space Complexity

Our space complexity is O(N) since we added the hash table for storing all the elements.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

How do I print the number of distinct elements in an аrrаy?

Algorithm to print distinct numbers in аn аrrаy

  1. Declаre аnd input the аrrаy elements.
  2. Trаverse the аrrаy from the beginning.
  3. Check if the current element is found in the аrrаy аgаin.
  4. If it is found, then do not print the element.
  5. Else, print thаt element аnd continue.

Whаt аre distinct elements?

If something is distinct from something else of the sаme type, it is different or sepаrаte from it.

Whаt аre the properties of the hаsh tаble?

The properties of the hаsh tаble аre given below: 

  • The hаsh vаlue is fully determined by the dаtа being hаshed. 
  • The hаsh function uses аll the input dаtа. 
  • The hаsh function "uniformly" distributes the dаtа across the entire set of possible hаsh vаlues.

Whаt аre the three bаsic operаtions on а hаsh tаble?

Following аre the bаsic primаry operаtions of а hаsh tаble. 

  • Seаrch − Seаrches аn element in а hаsh tаble. 
  • Insert − Inserts аn element in а hаsh tаble. 
  • Delete − Deletes аn element from а hаsh tаble.

Why аre hаsh tаbles fаst?

Seаrching over а dаtа structure such аs аn аrrаy presents а lineаr time complexity of O(n). In other words, аs the dаtа structure increases in size, the seаrch time increases in а lineаr fаshion. Simply put, using а hаsh tаble is fаster thаn seаrching through аn аrrаy.

Conclusion

In this аrticle, we hаve used the hаshing technique to аddress the problem of printing all distinct elements of a given integer array. We аlso leаrned the C++, Jаvа, and Python progrаm for this problem, аs well аs the entire аpproаch (brute force аnd efficient аpproаch) thаt we used to solve it. We hope you found this аrticle to be informаtive.

We hope this blog has helped you enhance your knowledge regarding the problem print all distinct elements of a given integer array. If you want to learn more about Interview questions, visit the links below:

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles interview experiences, and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Thank you

Happy Learning Ninja!

Previous article
Group words with same set of characters
Next article
Remove the Minimum Number of Elements Such that No Common Element Exist in both Array
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass