Unique Number I

Given a unsorted array arr[] of positive integers having all the numbers occurring exactly twice, except for one number which will occur only once. Find the number occurring only once.

Examples :

Input: arr[] = [1, 2, 1, 5, 5]
Output: 2
Explanation: Since 2 occurs once, while other numbers occur twice, 2 is the answer.

Input: arr[] = [2, 30, 2, 15, 20, 30, 15]
Output: 20
Explanation: Since 20 occurs once, while other numbers occur twice, 20 is the answer.

Constraints
1 ≤ arr.size() ≤ 10⁶
0 ≤ arr[i] ≤ 10⁹

Approach 01:

class Solution {
public:
    int findUnique(const vector<int>& nums) {
        unordered_map<int, int> frequencyMap;

        for (int num : nums)
            ++frequencyMap[num];

        for (const auto& [element, count] : frequencyMap)
            if (count == 1)
                return element;

        return -1;
    }
};

class Solution:
    def findUnique(self, nums):
        frequencyMap = {}
        
        for num in nums:
            frequencyMap[num] = frequencyMap.get(num, 0) + 1
        
        for element, count in frequencyMap.items():
            if count == 1:
                return element
        return -1

Time Complexity:

• First Loop (Frequency Count):

  We iterate through the entire nums array once → \( O(n) \)

• Second Loop (Find Unique):

  We iterate through the frequency map entries. In the worst case, all elements are unique → \( O(n) \)

• Total Time Complexity:

  \( O(n) \)

Space Complexity:

• Hash Map:

  Stores frequency of up to \( n \) elements → \( O(n) \)

• Total Space Complexity:

  \( O(n) \)