Find The Repeating And Missing Number
You are given an array 'nums' consisting of first N positive integers. But from the N integers, one of the integers occurs twice in the array, and one of the integers is missing. You need to determine the repeating and the missing integer.

Example:

Let the array be [1, 2, 3, 4, 4, 5]. In the given array ‘4’ occurs twice and the number ‘6’ is missing.

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array. The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, print the two space-separated integers denoting the repeating and the missing numbers, in the same order.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this in O(N) time and O(1) space complexities?

Constraints:

1

Question

Find The Repeating And Missing Number

You are given an array 'nums' consisting of first N positive integers. But from the N integers, one of the integers occurs twice in the array, and one of the integers is missing. You need to determine the repeating and the missing integer.

Example:

Let the array be [1, 2, 3, 4, 4, 5]. In the given array ‘4’ occurs twice and the number ‘6’ is missing.

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, print the two space-separated integers denoting the repeating and the missing numbers, in the same order.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this in O(N) time and O(1) space complexities?

Constraints:

1 <= T <= 100 
2 <= N <= 10^4
1 <= nums[i] <= N

Time Limit: 1 sec

Accepted Answer

Sort the Array

A simple and intuitive approach could be to sort the given array in ascending order.
Now, in order to determine the repeating and the missing numbers, we check the adjacent pair of elements.
If two numbers are equal and are adjacent to each other, it implies that the number occurs twice. Hence, it is the repeating number.
In order to determine the missing element, we maintain a counter.
The counter holds the next expected number in the array. So, initially counter holds 1.
Now, we iterate through the array.
If the current number is equal to the counter,
- We increment the counter.
- And check if the current number is the repeating number. If so, we skip the next number.
- Otherwise, move to the next number.
Otherwise, if the current number is not equal to the counter, we have found the missing number.
- The counter holds the missing number.
Return the repeating and the missing number.

Space Complexity: O(1)Explanation:

O(1) per test case.

In the worst case, no extra space is required.

Time Complexity: O(nlogn)Explanation:

O(N * logN) per test case, where N is the number of elements in the array.

In the worst case, sorting requires O(N*logN) time and determining the repeating and the missing number requires O(N) time. Hence, the overall complexity is O(N*logN).

Accepted Answer

Using Frequency Array

The idea here is that all the numbers except the missing and the repeating number will have a frequency count equal to 1.
The missing number will have zero frequency whereas the repeating number will have a frequency equal to the 2.
Hence, using the frequency of the numbers present in the array we can determine the repeating and the missing element.
In order to implement this approach, we use a count array to store the frequency.
We initialize the count array to zero for all the numbers.
Now, iterate through the array and increment the corresponding frequency count of the numbers.
Now, we iterate through the count (frequency) array.
The number with a frequency equal to zero is the missing number while the number with a frequency equal to two is the repeating number.

Note:

Instead of using a frequency array, we can also use a hashmap to store the counts corresponding to each number or a visited array to keep a track of which numbers have been encountered.
- In the case of a visited array, the number which has not been visited is the missing number and the number which has been visited twice is the repeating number.
The implementation of hashmap and visited array will be similar to this approach.
Also, both approaches will have the same time and space complexity.

Space Complexity: O(n)Explanation:

O(N) per test case.

In the worst case, extra space is by frequency array.

Time Complexity: O(n)Explanation:

O(N) per test case, where N is the number of elements in the array.

In the worst case, we iterate over the given array and the frequency array. Hence the overall complexity is O(N + N) = O(N).

Accepted Answer

Using Sum and Sum of Squares of Numbers

The idea here is to generate two equations using the sum and sum of squares of the N numbers and use them to determine the repeating and the missing element.
Let us assume that the repeating number is X and the missing number is Y.
We know that the given array contains the first N positive integers in which the number Y is missing and number X occurs twice.
Therefore, using the formula for the sum of first N positive integers, i.e. N * (N + 1) / 2, we can say:
- N * (N + 1) / 2 + X - Y = SumOf(Array[0, N-1])
- i.e. X - Y = SumOf(Array[0, N - 1]) - N * (N + 1) / 2
- I.e. X - Y = S, where S = SumOf(Array[0, N - 1]) - N * (N + 1) / 2.
Also, using the formula for the sum of squares of first N positive integers, i.e. N * (N + 1) * (2N + 1) / 6, we can say:
- (1^2 + 2^2 + 3^2…..+N^2) + X^2 - Y^2 = A[0]^2 + A[1]^2 + …….. + A[N-1]^2
- N * (N + 1) * (2N + 1) / 6 + X^2 - Y^2 = SumOfSquares(Array[0, N-1])
- i.e. X^2 - Y^2 = SumOfSquares(Array[0, N-1]) - SumOfSquares(1, N)
- i.e. X^2 - Y^2 = SqrSum, where SqrSum = SumOfSquares(Array[0, N-1]) - SumOfSquares(1, N).
Now, using the previous equation, we get:
- X + Y = SqrSum / S
Solving the two equations we can determine the value of X and Y.
An important point to note here is that the above solution can cause integer overflow.

Space Complexity: O(1)Explanation:

O(1) per test case.

In the worst case, no extra space is required.

Time Complexity: O(n)Explanation:

O(N) per test case, where N is the number of elements in the array.

In the worst case, we iterate over the complete given array to determine the sum and sum of squares of its numbers. Hence the overall complexity is O(N).

Accepted Answer

Using XOR Operation

The idea here is to use the property of XOR operations which is, XOR of the two equal numbers results in zero, i.e. the numbers cancel out each other.
Firstly, we calculate the XOR of all the elements of the array and store it in a variable say, xorArray.
We also calculate the XOR first N positive integers and store it in a variable say, xorN.
Now, if we XOR the above two values, then the common elements in the two will cancel out each other and we will be left with XOR of the repeating and the missing number. Store this result in another variable, say xorResult.
Now, in order to determine the repeating and the missing number, we use another property of XOR i.e. XOR outputs true only when inputs differ.
So, we can say, all the bits that are set in xorResult will be set in either the repeating number or the missing number. But not in both.
Now, we take any one of the set bits in the xorResult (here we have taken the rightmost set bit) and divide the elements of the array into two sets – one containing elements with the same bit set and other with the same bit not set.
We find the XOR of these two sets and store it in variables say, X and Y respectively.
By doing so we have separated the repeating and the missing element into two different sets. But we don’t have their exact values.
Now, we XOR X with the first N positive integers which have the rightmost bit set and Y with the integers which have the rightmost bit unset. This cancel outs the common elements and we are left with the required numbers.
By doing so, we have determined the repeating and the missing numbers (stored in X and Y). But we still don’t know which one is which.
To determine this we iterate through the array to check which of the two numbers, X or Y, is missing.
Then the other element will be the repeating number.
Note: Using XOR does not cause integer overflow.

Space Complexity: O(1)Explanation:

O(1) per test case.

In the worst case, no extra space is required.

Time Complexity: O(n)Explanation:

O(N) per test case, where N is the number of elements in the array.

In the worst case, we iterate over the given array and the first N positive integers. Hence the overall complexity is O(N).

Accepted Answer

Using Given Array to Track Visited Numbers

The idea here is to use the given array itself to keep track of visited numbers.
This can be done by using the absolute value of a number as an index and marking the corresponding number present at that index.
A number can be marked by negating its value.
As a number can get marked even before it is reached in the traversal we use the absolute value of a number as an index.
So, the above approach can be implemented by traversing the array and marking the index corresponding to the current number.
While traversing if the index corresponding to the current number has already been marked. Then the current number is the repeating number in the array.
In order to determine the missing number, traverse the array again and look for a positive value.
The index corresponding to the positive number gives us the missing number (= index + 1).

Space Complexity: O(1)Explanation:

O(1) per test case.

In the worst case, no extra space is required.

Time Complexity: O(1)Explanation:

O(N) per test case, where N is the number of elements in the array.

In the worst case, we iterate over the given array twice. Hence the overall complexity is O(N + N) = O(N).

You are given an array 'nums' consisting of first N positive integers. But from the N integers, one of the integers occurs twice in the array, and one of the integers is missing. You need to determine the repeating and the missing integer.

Example:

Input format:

Output format:

Note:

Follow Up:

Constraints:

Top Oracle Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern