Last Updated: 15 Sep, 2020
Single Number III
Moderate
Asked in companies
Given an array 'ARR' of integers of size N in which two elements appear exactly once and all other elements appear exactly twice. Your task is to find the two elements that appear only once.
Note
1. Input will always have only two integers that appear exactly once rest will appear twice.
2. Try to do this in linear time and constant space.
Input Format:
The first line of input contains an integer N representing the size of the array.
The second line of input contains an N space-separated integers representing the array elements.
Output Format:
Print the two space-separated elements that appear only once where the first integer is less than the second integer.
Constraints:
2 <= N <= 10^5
-10^5 <= ARR[i] <= 10^5
Time Limit: 1 sec
Approaches
- We will maintain a list or vector to store the two elements that appear only once.
- We will run a loop from i = 0 to i = N - 1 and for i’th loop, we need to check if there is another element with the same value is present or not so we will run another loop from j = 0 j = N - 1 and if i is not equal to j check if ARR[i] is equal to ARR[j]. If it is equal for any j that means i’th element is repeated otherwise add the i’th element to the list.
- Now print the answer as mentioned in the problem statement.
We will sort the array and run a loop from i = 0 to i = N - 1 and for i’th element check its adjacent element if any one of the adjacents is same then skip this element otherwise we can print this and it will be in sorted order which satisfies the criteria of the problem statement also.
- We will be using a hashmap and increase the count for each element in the hashmap.
- Again iterate in the hashmap and if the occurrence is 1 then add it to the list.
- Now print the answer as required.
- First of all, we will find the xor of all the elements since every element occurs twice except the two elements which occur once. So we will have the xor of those two elements let’s call it ‘XOR_OF_ARRAY’ and let’s define two more variables FIRST_ELEMENT and SECOND_ELEMENT to store our answer.
- Now, find any set bit in the XOR_OF_ARRAY and now traverse the whole element again and separate them on the basis of the set bit. If the current element has the same bit set as that of the XOR_OF_ARRAY then take the xor of this element with the FIRST_ELEMENT otherwise take the xor of this element with the SECOND_ELEMENT.
- If we separate the elements on the basis of a set bit of XOR_OF_ARRAY and then take their xor it will make those repetitive elements to 0 and FIRST_ELEMENT and SECOND_ELEMENT will have the non-repetitive elements.
- Now print the answer as required.