All Repeating Except Two
Try First, Check Solution later1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.
1. You are given an array of numbers.Input Format
2. You have to find 2 non-repeating numbers in an array.
3. All repeating numbers are repeating even number of times.
A number nOutput Format
2 Non-repeating numberQuestion Video
1 <= n <= 10^9Sample Input
1 <= a1,a2.. <= 10^9
23 27 23 17 17 37
The problem here deals with finding two non-repeating elements in an input array where every other element repeats twice. Here lets suppose we have non-repeating 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 dead-end. Now let us try to take the XOR of the non-repeating 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 non-repeating elements.
The RSB Mask of our XOR result for non-repeating elements would be [ 0 0 0 0 1 0 ]. This implies that at the 1st index there is a difference of bits in the non-repeating 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 non-repeating elements in different sets. This was possible since segregating at 1st index ensured that firstly both non-repeating 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 non-repeating 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