22. Unique Number I

The problem can be found at the following link: Question Link

Problem Description

You are given an unsorted array of positive integers in which every element occurs exactly twice, except for one element that appears only once. Your task is to find that unique number.

Examples

Example 1:

Input:

arr[] = [1, 2, 1, 5, 5]

Output:

2

Explanation:

All elements except 2 occur twice. Hence, the unique number is 2.

Example 2:

Input:

arr[] = [2, 30, 2, 15, 20, 30, 15]

Output:

20

Explanation:

Only 20 appears once. All other elements occur twice.

Constraints:

• $(1 \leq \text{arr.size()} \leq 10^6)$

• $(0 \leq \text{arr}[i] \leq 10^9)$

My Approach

Bit Manipulation (XOR Method)

• The XOR of two equal numbers is 0.

• XOR of a number with 0 is the number itself.

• Thus, XOR-ing all numbers will cancel out the duplicates and leave the unique one.

Algorithm Steps:

1. Initialize result as 0.

2. Iterate over the array and XOR each number with the result.

3. Final result is the unique number.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), as we traverse the array once.

• Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of extra space.

Code (C++)

class Solution {
  public:
    int findUnique(vector<int> &a) {
        int r = 0;
        for (int x : a) r ^= x;
        return r;
    }
};

⚡ Alternative Approaches

📊 2️⃣ Hash Map Frequency Count

Algorithm Steps:

1. Traverse the array and store frequencies in a hash map.

2. Return the element with frequency 1.

class Solution {
  public:
    int findUnique(vector<int> &a) {
        unordered_map<int, int> freq;
        for (int x : a) freq[x]++;
        for (auto it = freq.begin(); it != freq.end(); ++it)
            if (it->second == 1) return it->first;
        return -1;
    }
};

📝 Complexity Analysis:

• Time Complexity: O(n)

• Space Complexity: O(n)

✅ Why This Approach?

Straightforward and useful when duplicates can appear more than twice or in non-pair counts.

📊 3️⃣ Sorting and Pair Check

Algorithm Steps:

1. Sort the array.

2. Compare elements in pairs. The one not matching its pair is unique.

class Solution {
  public:
    int findUnique(vector<int> &a) {
        sort(a.begin(), a.end());
        int i = 0, n = a.size();
        while (i < n - 1) {
            if (a[i] != a[i + 1]) return a[i];
            i += 2;
        }
        return a[n - 1];
    }
};

📝 Complexity Analysis:

• Time Complexity: O(n log n)

• Space Complexity: O(1)

✅ Why This Approach?

Good when extra space isn’t allowed but we can afford sorting time.

🆚 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
XOR Method	🟢 O(n)	🟢 O(1)	Fastest, minimal space	Only works with exact pairs
Hash Map Frequency	🟢 O(n)	🔴 O(n)	Easy to extend to generic cases	Extra memory used
Sorting + Pairing	🔴 O(n log n)	🟢 O(1)	No extra memory, simple comparison	Slower due to sorting

✅ Best Choice?

Scenario	Recommended Approach
✅ Optimal runtime and no extra space	🥇 XOR Method
✅ Handles non-standard frequencies	🥈 Hash Map Frequency
✅ Array can be modified and space is a concern	Sorting + Pair Check

🔹 Overall Best for performance and space: XOR Method 🔹 Best for generic input flexibility: Hash Map Approach

Code (Java)

class Solution {
    public int findUnique(int[] arr) {
        int r = 0;
        for (int x : arr) r ^= x;
        return r;
    }
}

Code (Python)

class Solution:
    def findUnique(self, arr):
        r = 0
        for x in arr: r ^= x
        return r

Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count