Find Non - Repeating Numbers

Easy

0/40

Average time to solve is 15m

38 upvotes

Asked in companies

Problem statement

You are given an array of integers ‘A’ having ‘N’ number of elements. It is given that all the numbers in the array occur twice except the two numbers that appear only one time. You need to find those two non-repeating numbers.

For Example:

If the given array is [ 4, 7, 3, 2, 7, 2 ], you have to find ‘4’ and ‘3’ as 4 and 3 occur one time, and the rest of the elements ( 7 and 2 ) are occurring twice.

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

Input Format:

The first line contains a single integer T representing the number of test cases.      

The first line of each test case contains a single integer ‘N’, denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the given array.

Output Format:

For each test case, print two space-separated integers that denote the two non-repeating numbers in the given array.

Print the output of each test case in a new line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
4 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit: 1 sec

Sample Input 1:

2
4
2 4 7 2
8
3 9 3 1 4 8 1 9

Sample Output 1:

4 7
4 8

Explanation Of Sample Input 1:

Test Case 1: The given array is [ 2, 4, 7, 2 ].  4 and 7 are the two non-repeating numbers. Hence the output will be 4 and 7.

Test Case 2: Numbers 3, 1, 9 occurs two times while 4 and 8 occur once. Hence the output will be 4 8

Sample Input 2:

2
6
11 2 6 11 6 5
4
3 5 5 7

Sample Output 2:

2 5
3 7

Hint 1

Hint 2

Try to sort the given array and find the non-repeating elements by comparing adjacent elements.

Approaches (2)

Approach 1

Approach 2

Using Sorting

The simple idea is to sort the elements and compare every element with its adjacent elements. If any element A[i] is neither equal to its left nor to its right element, A[i] is a non-repeating element.

Algorithm

Sort the elements of the given array using any sorting algorithm.
Initialize an array ‘res’ to store the non-repeating elements.
If any element A[i] is not equal to its left and right adjacent element, add A[i] to ‘res’.
Return ‘res’

Time Complexity

O(N*log(N)), where ‘N’ is the number of elements in the array.

We are sorting the elements of the array which takes O(N*log(N)) time Therefore time complexity is O(N*log(N)).

Space Complexity

O(1)

No extra space is used. So the space complexity is O(1).

(100% EXP penalty)

Find Non - Repeating Numbers

Console