One Repeating And One Missing
1. You are given an array of length n containing numbers from 1 to n.Input Format
2. One number is present twice in array and one is missing.
3. You have to find these two numbers.
A number nOutput Format
a1
a2..
n numbers
Missing numberQuestion Video
Repeating Number
1 <= n <= 10^9Sample Input
1 <= a1,a2.. <= 10^9
7Sample Output
1
3
4
5
1
6
2
Missing Number > 7
Repeating Number > 1

Editorial
The problem here is that we are given an input array with numbers 1 to n but due to some reason a number is missing and in that position another number from the set repeats itself, now we wish to find the repeating and the missing number.
Consider the following example:
Input array: [ 3, 6, 2, 5, 1, 2, 7 ]
In this array, we can observe that 2 is the repeating number and 4 is the missing number.
To solve this problem if we would try taking XOR of the array that would serve no use as the XOR would cancel out the repeating number and the result would be meaningless. So to get our result we would add repetition to our input array and that repetition would be the original numbers that should be present i.e. numbers from 1 to n (here 1 to 7).
Now if we try to take XOR of the array we would get:
Now we can observe that the XOR result is the XOR of the repeating element and the nonrepeating element. Now we have successfully converted our problem to All Repeating except two, the difference only lies in the fact that our repeating number occurs thrice which can be considered as a pair of repeating with an extra occurrence so the problem remains the same. Now we can easily implement the segregation approach in our earlier problem All Repeating except two, to get our result.
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