Redirecting to
NADOS

One Repeating And One Missing

  Prev   Next

Try First, Check Solution later

1. 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 length n containing numbers from 1 to n.
2. One number is present twice in array and one is missing.
3. You have to find these two numbers.
Input Format 
A number n
a1
a2..
n numbers
Output Format 
Missing number
Repeating Number
Question Video
Constraints 
1 <= n <= 10^9
1 <= a1,a2.. <= 10^9
Sample Input 
7
1 
3 
4 
5 
1 
6 
2
Sample Output 
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 non-repeating 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






Video Solution

Code Solution

Run
 
Run
Id Name