Two Non-Repeating Elements
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

Question

Two Non-Repeating Elements

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

Accepted Answer

Brute Force

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.

Space Complexity: O(1)Explanation:

O(1), We are using constant extra space.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the size of the array.

We are using two nested for loops of size N each in each iteration therefore the time complexity here becomes of the order O(N^2).

Accepted Answer

Sorting

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.

Space Complexity: O(1)Explanation:

O(1), We are using constant extra space.

Time Complexity: O(nlogn)Explanation:

O(N * Log(N)), where N is the size of the array.

Since we are sorting the array first and then finding out the two non-repeating elements required.

Accepted Answer

Mapping

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.

Space Complexity: O(n)Explanation:

O(N), where N is the size of the array.

We are using a hash map to store the count of each element i.e. N elements.

Time Complexity: O(n)Explanation:

O(N), where N is the size of the array.

We are visiting every element once while updating its count in the hash map and once more when checking the count or frequency of each element.

Accepted Answer

Bit masking

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.

Space Complexity: O(1)Explanation:

O(1), We are using constant extra space.

Time Complexity: O(1)Explanation:

O(N), where N is the size of the array.

Since we are running for loops of size N two separate times only to calculate the XOR_OF_ARRAY array and then for finding the two non-repeating elements.

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

Input Format:

Output Format:

Constraints:

Top TO THE NEW Technical Trainee interview questions & answers

Popular interview questions of Technical Trainee