Last Updated: 30 Dec, 2020
Find Odd Occurrence Element
Easy
Asked in companies
You are given an array of 'N' elements. In this given array, each element appears an even number of times except one element which appears odd no. of times. Your task is to find the element which occurs an odd number of times.
For example :
Input array [5,5,6,4,6],If we look at the frequency of different elements in this array.We can see,4 appears an odd number of times, so our answer will be 4.
Input Format :
The first line of input contains a single integer 'T', representing the number of test cases.
Then the 'T' test cases follow.
The first line of each test case contains a number 'N' denoting the size of the array.
The second line contains 'N' space-separated distinct integers denoting elements of the array.
Output format :
For each test case print the element which appears an odd number of times.
The output of every test case will be printed in a separate line.
Note :
You don’t have to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1<= T <=100
1 <= N <= 10000
1 <= ARR[i] <= 10^8
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, and 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.
Time limit : 1 sec
Approaches
We will find the frequency of all elements by iterating over the whole array N times. On completion of iteration if the frequency of element is odd. We will return this element else keep on iterating.
- Let’s say we have a given array ARR and pair sum K.
- Iterate over ARR[i] for each 0 <= i < N and do:
- COUNT=0
- Iterate over ARR[j] for each 0 <= j < N and do:
- If ARR[i] = ARR[j] then increase COUNT by 1.
- If COUNT is odd then return ARR[i].
We will scan the array from left to right and we will use the Hash to store frequency of each element. On encountering an element we will increase its hash value by 1.No we will scan again and check the Hash value of each element and we can find the element with odd frequency.
- Let's say we have given an array ARR.
- We are using an unordered_map called MYMAP as Hash.
- Iterate over ARR[i] for each 0 <= i < N and do:
- MYMAP[ARR[i]] += 1
- Iterate over ARR[i] for each 0 <= i < N and do:
- If MYMAP[ARR[i]] is odd then return ARR[i]
As XOR value of two same elements is zero and XOR of any element, say X, with 0 is X.We can use this fact in our problem, as if we XOR all elements of the array, then elements which appear even no. of time will always add 0 to result. So the result will have only one element which appears odd no. of time.
Algorithm :
- Initialize an integer variable RESULT=0
- Let's say we have given an array ARR.
- Iterate over ARR[i] for each 0 <= i < N and do:
- RESULT = RESULT ^ ARR[i] (where ^ is XOR operator)
- Return RESULT.