Missing and repeating numbers

Moderate
0/80
Average time to solve is 25m
349 upvotes
Asked in companies
AmazonMathworksOracle

Problem statement

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?
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains an integer ā€˜Nā€™ denoting the size of the array.
The second line contains ā€˜Nā€™ space-separated integers.
Output Format: 
Print the missing number (M) and the repeating number (R) separated by a single space.
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: 
2 <= N <= 5 * 10^4
1 <= data <= N

Where ā€˜Nā€™ is the size of the array and ā€˜dataā€™ denotes the value of the elements of the array.
Hint

Can you do this by applying brute force? 

Approaches (5)
Brute Force

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. 

Time Complexity

O(N * N) where N is the number of elements in the array.

 

For every element in the array, we are traversing the rest of the array. The total operations performed will be (N * (N - 1) / 2). Thus, the final time complexity is O(N * (N - 1 ) / 2) = O(N * N). 

Space Complexity

O(1) 

 

We are not using any extra data structure. Only constant additional space is required.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Missing and repeating numbers
Full screen
Console