Hey guys! So in this tutorial will be understanding this simple problem that is finding missing and repeating elements in a list of numbers. Let’s understand the problem through an example, consider the list of numbers given below for n = 6.
| 1 | 2 | 4 | 5 | 5 | 6 |
The missing number would be the number that is not present out of the numbers 1,2,3…. n and the repeating number would be the number that occurs in the element twice.
In the case mentioned above the missing number is going to be 3 and the repeating number is going to be 5. The actual result must look something like this: 1 2 3 4 5 6 to have no repeating and missing numbers.
Also read: Python lists vs Array
Finding Missing and Repeating Elements Manually
Now, the manual approach is to traverse the list one time and check the count of each number.
If the count of any number is equal to 2*n then we found the repeating number and then traverse through the elements to check for the occurrence of each number: one, two, three, and so on.
If any of those numbers are not present, then return that number as the missing number.
The problem with this approach is that this method is slow, introduces too many steps for a simple problem and, can just be done in a better manner.
A Better Method to Find Missing and Repeating Elements
So, we are going to create an extra array that will take into consideration if an element is visited or not. The size of the array is the same as that of the value of n.
Initially, all the values are equal to 0 (not seen) and the moment an element is seen in the array, its value in the final array is set to 1 (seen).
This continues till the end of the array. We have to compute two things: the repeating number and the missing number.
If at any point, the number whose value is being set is already set then this implies that this number is the repeating number.
Now to compute the missing number, we will be traversing through the final array one last time and checking which number’s value in the final array is still 0. This implies that the number was never seen and hence it’s the missing number in the array.
We will be returning the two values in form of a list having two values: first the repeating number and second the missing number.
Implementating in Python
I hope this is clear to you. Now let us look at the code implementation for finding missing and repeating elements and a sample output of the code.
def find_miss_repeat(arr,n):
final_array = [0 for i in range(n)]
l = [0,0]
for i in arr:
if(final_array[i-1]==1):
l[0] = i
else:
final_array[i-1] = 1
for i in range(len(final_array)):
if(final_array[i]==0):
l[1] = i+1
return l
x = find_miss_repeat([1,2,4,5,5,6],6)
print("Repeating Number: ",x[0])
print("Missing Number: ",x[1])
The output of the code is shown below.
Repeating Number: 5
Missing Number: 3
Conclusion
I hope the concept is clear to you. You can try it by yourself using both the naive and the quick methods. The same logic is applicable to all the programming languages as well.
Thank you for reading the tutorial! Happy coding! 😇