Hashing: Given an array, find the element that occurs odd number of times

Coding Interview Questions

1 min read

Problem Statement:

Given an array, find the element that occurs odd number of times

Example:

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

Output: 1

Solution Explanation:

We will use hashmap to solve the problem.

We will iterate through the array, add them into the hash table and increment the count.

Then iterate through the hashmap and print which occurs odd number of time.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;

int solution(vector<int> arr) 
{
   int n = arr.size();
   unordered_map<int, int> mp;

    for(int i = 0; i < n; i++)
    {
        mp[arr[i]]++;
    }

    for(auto i : mp)
    {
        if(i.second % 2 != 0)
        {
            return i.first;
        }
    }
    return -1;
}

int main() 
{ 
    vector<int>arr { 1, 1, 1, 2, 2, 3, 3}; 

    cout << solution(arr); 

    return 0; 
}