Unique Number III

Given an array of integers arr[] where, every element appears thrice except for one which occurs once.
Find that element which occurs once.

Examples:

Input: arr[] = [1, 10, 1, 1]
Output: 10
Explanation: 10 occurs once in the array while the other element 1 occurs thrice.

Input: arr[] = [3, 2, 1, 34, 34, 1, 2, 34, 2, 1]
Output: 3
Explanation: All elements except 3 occurs thrice in the array.

Constraints:
1 ≤ arr.size() ≤ 10⁵
arr.size() % 3 = 1
-10⁹ ≤ arr[i] ≤ 10⁹

Approach 01:

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    int getSingle(vector<int>& arr) {
        map<int, int> frequencyMap;
        for (int num : arr) {
            ++frequencyMap[num];
        }
        // Return the element that appears exactly once
        for (const auto& [value, count] : frequencyMap) {
            if (count == 1)
                return value;
        }
        return -1;  // No unique element found
    }
};

from typing import List
from collections import Counter

class Solution:
    def getSingle(self, arr: List[int]) -> int:
        frequencyMap = Counter(arr)
        # Return the element that appears exactly once
        for value, count in frequencyMap.items():
            if count == 1:
                return value
        return -1  # No unique element found

Time Complexity:

• Building the Map:

  Each insertion into map takes \(O(\log n)\), and we do this for \(n\) elements → \(O(n \log n)\).

• Scanning for Unique Element:

  Iterate through at most \(n\) map entries → \(O(n)\).

• Total Time Complexity:

  \(O(n \log n)\).

Space Complexity:

• Map Storage:

  Stores up to \(n\) key–value pairs → \(O(n)\).

• Total Space Complexity:

  \(O(n)\).