Find Odd Occurrence Element

Easy
0/40
Average time to solve is 10m
profile
Contributed by
8 upvotes
Asked in companies
Expedia GroupPayPalCIS - Cyber Infrastructure

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample input 1 :
4
5
2 7 7 7 2
3
9 9 9
7
1 2 3 3 2 1 4
5
11 20 5 5 20
Sample output 1 :
7
9
4
11
Explanation for sample output 1 :
(i) For the first array, element 7 appears 3 times.
(ii) For the second array, element 9 appears 3 times.
(iii) For the third array, element 4 appears 1 time.
(iv) For the fourth array, element 11 appears 1 time.
Sample input 2 :
5
5
1 1 2 2 1
3
9 2 9
7
9 7 6 9 9 9 7
9
6 6 4 6 5 5 4 6 6 
1
10
Sample output 2 :
1
2
6
6
10
Explanation for sample output 2:
(i) For the first array, element 1 appears 3 times.
(ii) For the second array, element 2 appears 1 time.
(iii) For the third array, element 6 appears 1 time.
(iv) For the fourth array, element 6 appears 5 times.
(v) For the fifth array, there is only 1 element, so the answer is 10.
Hint

Think about iterating over the whole array and find the frequency of each element

Approaches (3)
Brute force

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.

  1. Let’s say we have a given array ARR and pair sum K.
  2. Iterate over ARR[i] for each 0 <= i < N and do:
    1. COUNT=0
    2. Iterate over ARR[j] for each 0 <= j < N and do:
      1. If ARR[i] = ARR[j] then increase COUNT by 1.
    3. If COUNT is odd then return ARR[i].
Time Complexity

O(N^2) where N is the length of the string.

 

We are iterating over the whole array for each element. So for N elements, the overall time complexity is O(N^2).

Space Complexity

O(1).

 

Constant memory is being used. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Find Odd Occurrence Element
Full screen
Console