Sorting: Print elements occurred only once in the array

Problem Statement:

You are given an array that has number repeating once or twice.

You need to identify the numbers that occurs once in an array.

Example:

Input: [1, 1, 2, 2, 4, 4, 3, 3, 6, 7, 7, 9]

Output: 6, 9

Solution 1: Sorting

Sort the array.

Compare element with its adjacent element.

If the element is not equal to the adjacent element, then print it.

Time Complexity: O(n log n)
Space Complexity: O(1)

Solution 2: Hashing

Use unordered map and insert all the elements with its occurrence in the unordered map

Traverse the map again and print the elements with occurrence 1

Time Complexity: O(n log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;


void solution_1 (int arr[], int n)
{
    sort(arr, arr + n);
 	
 	// check first element
    if (arr[0] != arr[1])
        cout << arr[0] << " ";
 
    for (int i = 1; i < n - 1; i++)
        if (arr[i] != arr[i + 1] && arr[i] != arr[i - 1])
            cout << arr[i] << " ";
 	
 	// check last element
    if (arr[n - 2] != arr[n - 1])
        cout << arr[n - 1] << " ";
}


void solution_2 (int arr[], int n)
{
    unordered_map<int, int> mp;
 
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;
 
    for (auto it = mp.begin(); it != mp.end(); it++)
        if (it->second == 1)
            cout << it->first << " ";
}

int main()
{
 
    int arr[] = { 7, 7, 6, 6, 1, 1, 2, 3, 4, 4, 3, 9, 8 };

    int n = sizeof(arr) / sizeof(arr[0]);
 
    solution_1(arr, n);
    cout<<"\n";
    solution_2(arr, n);
 
    return 0;
}

Output

2 8 9 
9 8 2