Missing and repeating numbers
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.
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.
- Sort the given array.
- Traverse the array from left to right and find the repeating number by comparing the adjacent numbers.
- 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, 5, 2, 2, 3 }.
After sorting the array, the array will become { 1, 2, 2, 3, 5 }.
When we traverse this array, we will see that the element at index one and index two is 2. 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.
- Create an array ‘countNumbers’ of size ‘n’ and initialize it with zero.
- Traverse the given array and update the count of every element in the array ‘countNumbers’ as follows :
countNumbers[curElement - 1] = countNumbers[curElement - 1] + 1
Where curElement is the current element that we are considering in the given array. - Now traverse the array ‘countNumbers’ and the index i at which we encounter a ‘0’ gives the missing number ( M = i + 1 ) and the index j at which we encounter ‘2’ gives us the repeated number ( R = j + 1 ).
The idea is to traverse the array and mark the visited elements.
While traversing the array, we will use the absolute value of every element as an index and make the value at this index as negative to mark it visited. For example, for element 3, we will make the value at index 2 as negative ( since the array is 0-indexed ). For any element in the array, if the element at the index {element - 1} is already marked negative, then this is the repeating element.
To find the missing number, we will traverse the array again and look for a positive value. The index at which we find the positive value is our missing number because that index is not present in the array as an element.
For Example: Consider the array Arr = { 1, 5, 2, 2, 3 }.
Now we will traverse the array and mark the visited numbers as follows:
- At index 0, we encounter 1. To mark this element as visited, Arr[1 - 1] = - Arr[1 - 1].
Current array Arr: {-1, 5, 2, 2, 3}.
- At index 1, we encounter 5. To mark this element as visited, Arr[5 - 1] = - Arr[5 - 1].
Current array Arr: {-1, 5, 2, 2, -3}.
- At index 2, we encounter 2. To mark this element as visited, Arr[2 - 1] = - Arr[2 - 1].
Current array Arr: {-1, -5, 2, 2, -3}.
- At index 3, again we encounter 2.
Here, the element at index 1 (2 - 1), is already negative. It means we have already visited it. Thus, we have found our repeating number ‘R’ which is 2.
Current array Arr: {-1, -5, 2, 2, -3}.
- At index 4, we encounter 3. To mark this element as visited, Arr[3 - 1] = - Arr[3 - 1].
Current array Arr: {-1, -5, -2, 2, -3}.
- To find the missing number ‘M’, we will again traverse the array.
- We will find that the element at index 3 is the only positive element. It means that the missing number is 3 + 1 = 4.
So, our missing number ‘M’ is 4 and the repeating number ‘R’ is 2.
We know that XOR of a number with itself is 0.
Now, let's start with the algorithm.
- Calculate XOR of all the elements of the array.
findXOR = arr[0]^arr[1]^arr[2]…..arr[n-1]
Now, XOR the result with all numbers from 1 to n.
findXOR = (findXOR)^1^2^…..^n.
- Now, findXOR will contain the XOR of the missing number and the repeating number as all the numbers would nullify each other.
- All the set bits in findXOR will be in either the missing number or the repeating number. Using any set bit in the findXOR, let's say the rightmost set bit, we can divide the elements of the given array in two sets.
- In the first set, we have the elements with the same bit set.
- In the second set, we have all the elements with the same bit not set.
- Initialize two variables, ‘bitSet’ and ‘bitNotSet’ with 0.
- Traverse the given array and if the element belongs to the first set, take its XOR with bitSet else take its XOR with bitNotSet.
- Traverse from 1 to n, and if the number belongs to the first set, take its XOR with bitSet else take its XOR with bitNotSet.
- Now, we have our missing and repeating numbers stored in bitSet and bitNotSet, but we do not know which one is missing and which one is repeating.
- To find which one is repeating, we will again traverse the given array and if ‘bitSet’ is present in the array, it means ‘bitSet’ is our repeating number and ‘bitNotSet’ is our missing number. We will store ‘bitSet’ in the variable ‘R’ and ‘bitNotSet’ in the variable ‘M’. If ‘bitNotSet’ is present in the array, it means ‘bitNotSet’ is our repeating number and ‘bitSet’ is our missing number. We will store ‘bitSet’ in the variable ‘M’ and ‘bitNotSet’ in the variable ‘R’.
- Finally, we will return the missing number ‘M’ and the repeating number ‘R’.
For example:
If the given array is [1, 3, 5, 3, 4]
Then, findXOR = [1 ^ 2 ^ 3 ^ 4 ^ 5] ^ [ 1 ^ 3 ^ 5 ^ 3 ^ 4] = 1
Notice that, 2 is our missing number and 3 is our repeating number in the given array and 2^3 is 1.
Now, the first bit is set in 1.
We will traverse the array and find all the elements whose this bit is set and take their XOR and store it in A. Also, we will take the XOR of all the elements in the array and from 1 to n whose this bit is not set and store it in B.
A = [ 1 ^ 3 ^ 3 ^ 5 ] ^ [ 1 ^ 3 ^ 5] = 3
B = [ 4 ] ^ [ 2 ^ 4] = 2
As 3 is present in the array, this cant be our missing number.
Thus, 2 is our missing number and 3 is our repeating number.
