Single Number

Given an array arr[] of positive integers where every element appears even times except for one. Find that number occurring an odd number of times.

Examples:

Input: arr[] = [1, 1, 2, 2, 2]
Output: 2
Explanation: In the given array all element appear two times except 2 which appears thrice.

Input: arr[] = [8, 8, 7, 7, 6, 6, 1]
Output: 1
Explanation: In the given array all element appear two times except 1 which appears once.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ arr.size() ≤ 10⁶
0 ≤ arr_i ≤ 10⁵

Approach 01:

#include <unordered_map>
#include <vector>

class Solution {
public:
    int getSingle(std::vector<int>& arr) {
        std::unordered_map<int, int> frequencyMap;

        for (int num : arr) {
            frequencyMap[num]++;
        }

        for (auto it = frequencyMap.begin(); it != frequencyMap.end(); ++it) {
            if (it->second % 2 != 0) {
                return it->first;  // Return the number that appears an odd number of times
            }
        }

        return -1;  // Return -1 if no such number exists
    }
};

import collections

class Solution:
    
    def getSingle(self,arr):
        frequencyMap = collections.Counter(arr)
        
        for key, value in frequencyMap.items():
            if value % 2 != 0:
                return key  # Return the number that appears an odd number of times
        
        return -1  # Return -1 if no such number exists

Time Complexity

• Frequency Map Creation:

  The function iterates through the input array once to create a frequency map. This operation takes \(O(n)\), where \(n\) is the number of elements in the array.

• Frequency Map Traversal:

  After creating the frequency map, the function iterates through the map to find the number that appears an odd number of times. This operation takes \(O(m)\), where \(m\) is the number of unique elements in the array. In the worst case, \(m\) can be equal to \(n\), leading to \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\).

Space Complexity

• Auxiliary Space:

  The space used by the frequency map grows with the number of unique elements in the array. In the worst case, it can store up to \(n\) unique elements, leading to \(O(m)\) space complexity. Again, in the worst case, this is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\).