Problem Statement

Given an array of integers where every element occurs twice except for one, which occurs only once, the task is to find and return that unique element.

Examples

Example 1:

Input: arr = [4, 3, 4, 3, 2]

Output: 2

Example 2:

Input: arr = [9, 5, 7, 5, 9, 8, 8]

Output: 7

Different Approaches

1 Brute Force Approach

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

int findUnique(vector<int> arr) {
    for (int i = 0; i < arr.size(); i++) {
        int count = 0;
        for (int j = 0; j < arr.size(); j++) {
            if (arr[i] == arr[j]) {
                count++;
            }
        }
        if (count == 1) {
            return arr[i];
        }
    }
    return -1; // If no unique element found
}

int main() {
    vector<int> arr = {9, 5, 7, 5, 9, 8, 8};
    cout << "Unique element is: " << findUnique(arr) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity:O(n^2)

Space Complexity:O(1)

2 Using Hash Map

Code Implementation in C++:

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

using namespace std;

int findUnique(vector<int> arr) {
    unordered_map<int, int> count;
    for (int num : arr) {
        count[num]++;
    }
    for (auto pair : count) {
        if (pair.second == 1) {
            return pair.first;
        }
    }
    return -1; // If no unique element found
}

int main() {
    vector<int> arr = {9, 5, 7, 5, 9, 8, 8};
    cout << "Unique element is: " << findUnique(arr) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity:O(n)

Space Complexity:O(1)

3 Using XOR Operator

XOR of a number with itself is 0. So if we XOR all elements, the unique number will be left.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

int findUnique(vector<int> arr) {
    int unique = 0;
    for (int num : arr) {
        unique ^= num;
    }
    return unique;
}

int main() {
    vector<int> arr = {4, 3, 4, 3, 2};
    cout << "Unique element is: " << findUnique(arr) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity:O(n)

Space Complexity:O(1)