Single Number III

Moderate

0/80

Average time to solve is 40m

20 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

8
2 4 6 8 10 2 6 10

Sample Output 1:

4 8

Explanation of the Sample Input1:

4 and 8 appear only once in the array and rest all other elements appear twice in the array and 4 is printed first because it is smaller than the other element 8.

Sample Input 2:

4
-1 -1 5 3

Sample Output 2:

3 5

Explanation of the Sample Input2:

3 and 5 appear only once in the array and rest all other elements appear twice in the array and 3 is printed first because it is smaller than the other element 5.

Hint 1

Hint 2

Hint 3

Hint 4

Try to do using the brute force method maybe using two for loop?

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

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.

Time Complexity

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).

Space Complexity

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

(100% EXP penalty)

Single Number III

Console