Find a number repeating and missing in an array in Python
In this post, we will find the number repeating and the number missing in an array in Python programming. You may encounter this problem in coding contests or competitive programming. Let’s start with understanding the problem. Here it is solved in Python but for those who code in C++, they may check this link.
Understanding the Problem: How to find the repeating and missing number in an array
The task is to find the missing and repeating number from the array of size n. The values in the array lie in the inclusive range from 1 to n. Let’s see an example;
array = [ 3, 4, 5, 1, 5]
In the above example, 2 is the missing number whereas, 5 is the repeating number. Note that the array will be unsorted. Also, only one number will be repeating and missed out.
3 4 5 1 5
Missing Number = 2
Repeating Number = 5
Those who are unfamiliar with competitive programming and how we fetch inputs need not worry. Here is the code.
size = int(input()) array_temp = input().split() array = [ int(i) for i in array_temp ]
Now, after taking input and converting the values into an integer, we will sort the array.
array.sort() ans_repeat = 0 ans_miss = 0 for i in range(size-1): if array[i]==array[i+1]: ans_repeat = array [i] elif array[i]+1 != array[i+1]: ans_miss = array[i]+1 else: if (ans_miss and ans_repeat): break continue if (not ans_miss): if array==1: ans_miss=size else: ans_miss=1 print("Missing Number = " , ans_miss) print("Repating Number = " , ans_repeat)
- After sorting, we will iterate our sorted array till size-1 and check for the repeating numbers. If the condition does not match, we will check for the missing number by adding 1 to the current value and equating it with the next integer.
- The if-condition under else statement is not mandatory but recommended. In competitive programming, the constraints are approx 10**5 (10 to the power 5). If the answers are before the complete iteration, then it will save us a lot of time.
- In the last, we have checked whether the ans_miss is updated or not. Cause if either the first or last value is missing, in both the cases, ans_miss will remain unchanged.
5 2 2 3 4 5 Missing Number = 1 Repating Number = 2 9 1 2 3 4 5 6 6 7 8 Missing Number = 9 Repating Number = 6 5 1 1 2 3 4 Missing Number = 5 Repating Number = 1 2 1 1 Missing Number = 2 Repating Number = 1 7 1 2 4 5 6 7 7 Missing Number = 3 Repating Number = 7