Last Updated: 17 Apr, 2022
One Odd Occurring
Easy
Asked in companies
Given an array ‘ARR’ of ‘N’ integers, where all the elements occur an even number of times and only one number occurs an odd number of times.
Find and return the number which occurs an odd number of times.
For example:
'N' = 5, 'ARR' = [1, 2, 3, 2, 3]
Output: 1
Except for number 1, all numbers occur an even number of times.
Input Format :
The first line contains a single integer, 'N', representing the size of the array.
The second line contains 'N' space-separated integers.
Output format :
The only line contains a single integer representing the number occurring odd number of times.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Approaches
Approach:
We will run two nested loops and count the occurrence of every element.
If at any moment, we are getting the count as odd, we will just print that element.
Algorithm :
- For i = 0 to ‘N’
- Initialize ‘count’ variable as 0
- For j = 0 to ‘N’
- If ‘ARR[j]’ is equal to ‘ARR[i]’
- Increase ‘count’
- If ‘ARR[j]’ is equal to ‘ARR[i]’
- If the ‘count’ is odd, return the ‘ARR[i]’
Approach:
We will hash be using a hash data structure, so here we will store the frequency of an element ‘ARR[i]’ at ‘hash[ARR[i]]’.
Each time we encounter a number ARR[i] we will increase the value of hash[ARR[i]]
Algorithm :
- Create a ‘hash[max(ARR[I])]’ array
- For I = 0 to ‘N’
- Increase ‘hash[ARR[I]]’ by 1
- For I = 0 to the maximum value in ‘ARR’ :
- If ‘hash[I]’ is odd
- Return I
- If ‘hash[I]’ is odd
Approach:
The bitwise Xor all elements of the array where even occurring elements on Xor will give 0 whereas odd occurring element on xor give us the number since its even occurrence will give 0.
Algorithm :
- Initialize a result ‘res’ variable as 0
- For i = 0 to ‘N’
- res = res XOR ARR[i]’
- Return ‘res’
Similar problems