Last Updated: 3 Mar, 2021
Single Number
Easy
Asked in companies
You are given an array A of length N, where N is always an odd integer. There are (N-1)/2 elements in the array that occur twice and one element which occurs once.
Your task is to find the only element that occurs once in the array.
Note: There are (N-1)/2+1 elements that are unique in the array.
Example:
Consider the array be 1,6,4,6,2,4,2
The integers 2, 4, 6 occur twice and only the integer 1 occurs once.
Input Format:
The first line contains an integer ‘N’, representing the length of the array.
The second line contains N space-separated integers of the array A.
Output Format:
Print the only integer which occurs once in the array.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
Explanation:
The key idea is while iterating the array count frequencies of all elements by hashing them.
And after iterating check which element occurs only once by looking at its frequency.
Algorithm:
- Iterate the elements in the array.
- On encounter of any element in the array increase its frequency by 1 in the hashmap.
- After completion of iteration lookup into all the elements in the map and return the element with frequency as 1.
Explanation:
The idea to xor all the elements in the array and return the final xor value. The idea is based on the following two facts :
- X (xor) 0 = X , i.e. xor of any integer with 0 gives the integer itself.
- X (xor) X = 0 , i.e. xor of two same integers gives 0.
In the problem, we will have (N-1)/2 values that occur twice which will result in 0 after xor. And the only value which will contribute to the final result is the integer occurring only once.
Algorithm:
- Initiate result as 0.
- Iterate in the array. When encountering every element update result with the result (xor) A[i].
- result = result (xor) A[i] , A[i] being the current value in the array.
- Return result.
Similar problems