Two Non-Repeating Elements

Posted: 15 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1
  • 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.
Try Problem