C++ program to print all the Non-repeated Numbers in an Array

In this article, we are going to see how to print all the non-repeating numbers in an array with use of STL?
Submitted by Radib Kar, on December 19, 2018

Problem statement: Write a C++ program to print all the non-repeated numbers in an array in minimum time complexity.

Input Example:

    Array length: 10
    Array input: 2 5 3 2 4 5 3 6 7 3
    Output:
    Non-repeated numbers are: 7, 6, 4

Solution

Data structures used:

    Unordered_map <int, int>

Key in the map is array value
Value of key is frequency

Algorithm:

Declare a map hash to store array elements as keys and to associate their frequencies with them.

    Unordered_map <int, int>hash;

For each array element
Insert it as key & increase frequencies. (0 ->1)
For same key it will only increase frequencies.

For i=0: n-1
	hash[array [i]]++;
End For

Now to print the non-repeated character we need to print the keys (array elements) having value (frequency) exactly 1. (Non-repeating)
Set an iterator to hash.begin().
iterator->first is the key (array element) & iterator->second is the value( frequency of corresponding array value)

IF
    Iterator->second > 1
    Print iterator->first (the array element)
END IF

Time complexity: O(n)

Explanation with example:

For this array: 2 5 3 2 4 5 3 6 7 3

The code:

for(int i=0;i<n;i++){//creating the map
    hash[a[i]]++;//for same key increase frequency
}

Actually does the following

    At i=0
    array[i]=2
    Insert 2 & increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            1

    At i=1
    array[i]=5
    Insert 5 & increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            1
    5	            1


    At i=2
    array[i]=3
    Insert 3 & increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            1
    5	            1
    3	            1

    At i=3
    array[i]=2
    Insert 2 increase frequency
    '2' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            1
    3	            1

    At i=4
    array[i]=4
    Insert 4 &increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            1
    3	            1
    4	            1

    At i=5
    array[i]=5
    '5' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            1
    4	            1

    At i=6
    array[i]=3
    '3' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            2
    4	            1

    At i=7
    array[i]=6
    Insert 6, increase frequency.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            2
    4	            1
    6	            1

    At i=8
    array[i]=7
    Insert 7, increase frequency.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            2
    4	            1
    6	            1
    7	            1

    At i=9
    array[i]=3
    '3' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            3
    4	            1
    6	            1
    7	            1

Thus, Elements with frequency 1 are: 7, 6, 4

C++ implementation to print all the Non-Repeated Numbers with Frequency in an Array

#include <bits/stdc++.h>

using namespace std;


void findNonRepeat(int* a, int n){
    //Declare the map
    unordered_map<int,int> hash;
    
    for(int i=0;i<n;i++){//creating the map
        hash[a[i]]++;//for same key increase frequency
    }
    
    cout<<"the nonrepeating numbers are: ";
    //iterator->first == key(element value)
    //iterator->second == value(frequency)
    
    for(auto it=hash.begin();it!=hash.end();it++)
    if(it->second==1)//frequency==1 means non-repeating element
    printf("%d ",it->first);
    
    printf("\n");
    
}

int main()
{
    int n;
    cout<<"enter array length\n";
    cin>>n;
    int* a=(int*)(malloc(sizeof(int)*n));
    
    cout<<"input array elements...\n";
    
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    
    //function to print repeating elements with their frequencies
    findNonRepeat(a,n);

    return 0;
}

Output

enter array length
10
input array elements...
2 5 3 2 4 5 3 6 7 3
the nonrepeating numbers are: 7 6 4