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.

Input Format

5
3 4 5 1 5

OUTPUT

Missing Number = 2
Repeating Number = 5

Taking Input

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 ]

Code

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[0]==1:
        ans_miss=size
    else:
        ans_miss=1

print("Missing Number = " , ans_miss)
print("Repating Number = " , ans_repeat)

1. 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.
2. 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.
3. 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.

OUTPUT

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

Also, see

• Different ways to represent infinity in Python
• Find the repeating and missing number in an array(C++)
• Check whether the password is in the standard format or not in Python