All Repeating Except Two
1. You are given an array of numbers.Input Format
2. You have to find 2 nonrepeating numbers in an array.
3. All repeating numbers are repeating even number of times.
A number nOutput Format
a1
a2..
n numbers
2 Nonrepeating numberQuestion Video
1 <= n <= 10^9Sample Input
1 <= a1,a2.. <= 10^9
6Sample Output
23 27 23 17 17 37
27
37

Editorial
The problem here deals with finding two nonrepeating elements in an input array where every other element repeats twice. Here lets suppose we have nonrepeating numbers as a and b. Now if we use the XOR approach as we did in the problem All Repeating Except One, then we would get a ^ b, which would not be of any use, so we have to come up with a different approach.
Consider the following example:
Input: [36, 50, 24, 56, 36, 24, 42, 50]
Now let us try to take the XOR of the input array then we would get [ 0 1 0 0 1 0 ] which is a deadend. Now let us try to take the XOR of the nonrepeating elements here that are 56 and 42, so 52 ^ 42 = [ 0 1 0 0 1 0 ] which is the same as the XOR of the entire input array. This is since every other element in the input array except 42 and 56 are repeating twice hence they would cancel out each other. So we conclude that [ 0 1 0 0 1 0 ] is the XOR of both the entire array and also the XOR of nonrepeating elements.
The RSB Mask of our XOR result for nonrepeating elements would be [ 0 0 0 0 1 0 ]. This implies that at the 1st index there is a difference of bits in the nonrepeating elements. Now we wish to segregate the input array concerning whether the 1st index bit is set or not. After segregating we would get:
Set 1: [ 36, 24, 56, 36, 24 ] => 1st index bit set to 0
Set 2: [ 50, 42, 50 ] => 1st Index bit set to 1
Now if we observe that in both sets every element repeats itself twice except one and we were also able to separate both nonrepeating elements in different sets. This was possible since segregating at 1st index ensured that firstly both nonrepeating would segregate and then in the entire array it ensured that only an odd number of elements would be present in any setting. Now taking XOR in both sets would yield us the nonrepeating elements.
Time Complexity: O(n)
The time complexity for the function is linear as we are traversing on every element at least once.
Space Complexity: O(1)
The space complexity for the function is constant.

Asked in Companies

Related Topics