Find The Repeating And Missing Number

Easy
0/40
Average time to solve is 10m
profile
Contributed by
47 upvotes
Asked in companies
AmazonSamsungPhonePe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
1 4 2 5 2
2
2 2
Sample Output 1:
2 3
2 1
Explanation For Sample Input 1:
For the first test case we have, array: [1, 4, 2, 5, 2] and N = 5.

In the given array ‘2’ occurs twice and the number ‘3’ is missing. Hence, we output 2 and 3 for the repeating and the missing number, respectively.

For the second test case we have, array: [2, 2] and N = 2.

In the given array ‘2’ occurs twice and the number ‘1’ is missing. Hence, we output 2 and 1 for the repeating and the missing number, respectively.
Sample Input 2:
3
4
1 2 2 3
10
1 3 4 5 5 6 7 8 9 10
3
1 2 2
Sample Output 2:
2 4 
2 5 
2 3
Hint

A simple and intuitive approach could be to sort the given array and determine the repeating and the missing number.

Approaches (5)
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.
Time Complexity

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).

Space Complexity

O(1) per test case.

 

In the worst case, no extra space is required.

Code Solution
(100% EXP penalty)
Find The Repeating And Missing Number
Full screen
Console