Missing and repeating numbers

Posted: 12 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array of size ‘N’. The elements of the array are in the range from 1 to ‘N’.

Ideally, the array should contain elements from 1 to ‘N’. But due to some miscalculations, there is a number R in the range [1, N] which appears in the array twice and another number M in the range [1, N] which is missing from the array.

Your task is to find the missing number (M) and the repeating number (R).

For example:
Consider an array of size six. The elements of the array are { 6, 4, 3, 5, 5, 1 }. 
The array should contain elements from one to six. Here, 2 is not present and 5 is occurring twice. Thus, 2 is the missing number (M) and 5 is the repeating number (R). 
Follow Up
Can you do this in linear time and constant additional space? 
Input Format
The first line of input contains an integer T, the number of test cases.
The first line of every test case contains an integer ‘N’ denoting the size of the array.
The second line of every test case contains ‘N’ space-separated integers.
Output Format:
For every test case, print the missing number (M) and the repeating number (R) separated by a single space. 
The output of each test case is printed in a separate line.
Note
You don’t have to print anything, it has already been taken care of. Just implement the function. 
You have to return a pair whose first element is the missing number ‘M’ and the second element is the repeating number ‘R’. 
Constraints:
1 <= T <= 10    
2 <= N <= 5 * 10^4
1 <= data <= N

Where ‘T’ is the number of test cases, ‘N’ is the size of the array and ‘data’ denotes the value of the elements of the array. 
Approach 1

For finding the repeating number,

  • Traverse the array from left to right. For every element we encounter, we will check whether this element is present in the remaining array or not.
  • If the current element is also present in the remaining array, it is the repeating number.
  • Else, we will check for the next element.
     

For finding the missing number, 

  • We will use a mathematical formula :

Missing number ‘M’ = N*(N+1)/2 - ( sum(givenArray) - repeating number ).

Where N * (N + 1) / 2 will give the sum of the numbers in the range [1, N].

 

For Example: Consider an array { 1, 2, 5, 2, 3 }. 

At index 0: 

We will check whether 1 (arr[0]) is present in the remaining array [2, 5, 2, 3] or not. Since 1 is present in the remaining array, we will move to the next number. 

At index 1: 

We will check whether 2 (arr[1])  is present in the remaining array [5, 2, 3] or not.

Since 2 is present in the remaining array, it is our repeating number. 

Thus, 2 is our repeating element ‘R’.

Now, for finding the missing element, we will use the below formula. 

M = N*(N+1)/2 + R - sum(givenArray)

M = 15 + 2 - 13

M = 4. 

Thus, our missing number is 4 and the repeating number is 2. 

Try Problem