How to find two missing numbers in an array using python

Problem: In a given array two numbers are missing. The array may be sorted or not. The actual length of the array is given. Find those two numbers with the help of programming.

Because it's a python tutorial, we will use python and XOR operations to solve this problem.

As we know,

A XOR A = ZERO

A XOR B = NON-ZERO

We'll use this logic to solve the given problem. Let's see how...

For example, the given array is,

Arr = {1, 2, 4 , 6}

In this case, if the array would be in the increasing from, then the length should have been six. But see, here, two numbers are missing. We can easily assume what those two digits are but, how do the program will find them?

Solution

Step 1

Do XOR operation between these two arrays

{the given array} XOR {the array according to the length (n)}

In this case,

{1^2^4^6} XOR {1^2^3^4^5^6}

= 3^5

= 6 = 0110 (in binary)

Step 2

Find the first rightmost set bit. In this case, (0110), the rightmost set bit is placed in the second position.

So, pos = 2

Step 3

Divide the given array into two arrays.

array_1 will contain all the numbers from the given array that has the first rightmost set bit according to the position found at Step 2.

array_2 will contain all the remaining numbers from the given array.

Let's see how to find the first rightmost set bit at position 2 of the numbers from the given array.

Binary Values

1:- 0001

2:- 0010

3:- 0011

4:- 0100

5:- 0101

6:- 0110

Look at the yellow marked numbers. The rightmost 2nd bit is a set(1) value.

Summarize,

array_1 = {2, 6}

array_2 = {1, 4}

Step 4

Now, divide the array(according to the given length) into two arrays according to the same logic discussed at Step 3.

Arr = {1, 2, 3, 4, 5, 6}

Arr_1 = {2, 3, 6} (2nd rightmost is a set bit)

Arr_2 = {1, 4, 5}

Step 5

Perform the XOR operation between (array_1 and Arr_1) and (array_2 and Arr_2)

first_missing_number = {array_1} XOR {Arr_1}

                                        = {2^6} ^ {2^3^6}

                                        = 3

second_missing_number = {array_2} XOR {Arr_2}

                                        = {1^4} XOR {1^4^5}

                                        = 5

Code

'''Find two missing numbers in an array'''
def find_rightmost_set_bit(n):
    pos = 0
    count = 0
    while(n):
        count += n & 1
        n >>= 1
        pos += 1
        if count == 1:
            break
    return pos

def check_rightmost_bit(n, position):
    i = 1
    count = 0
    while(i <= position):
        count = n & 1
        n >>= 1
        i += 1

    if count != 0:
        return 1
    else:
        return 0

def find_missing_number(arr, length, actual_length):
    num1 = arr[0]
    num2 = 0
    for i in range(1, length):
        num1 = num1 ^ arr[i]

    for i in range(1, length + 3):
        num2 = num2 ^ i

    final_xor = num1 ^ num2
    position = find_rightmost_set_bit(final_xor)

    arr_of_set = []
    arr_of_unset = []

# Operation For the Given Array
    for i in range(0, length):
        status = check_rightmost_bit(arr[i], position)
        if status == 1:
            arr_of_set.append(arr[i])
        else:
            arr_of_unset.append(arr[i])

# Operation For Array(according to the length)
    array_of_all_set = []
    array_of_all_unsetset = []
    for j in range(1, actual_length+1):
        flag = check_rightmost_bit(j, position)
        if flag == 1:
            array_of_all_set.append(j)
        else:
            array_of_all_unsetset.append(j)

#==============Final Operation=================
# Finding the first missing number
    p1 = arr_of_set[0]
    p2 = array_of_all_set[0]
    for k in range(1, len(arr_of_set)):
        p1 = p1 ^ arr_of_set[k]

    for l in range(1, len(array_of_all_set)):
        p2 = p2 ^ array_of_all_set[l]

    first_missing_number = p1 ^ p2
    print(f"The First missing number is: {first_missing_number}")

# Finding the second missing number
    p3 = arr_of_unset[0]
    p4 = array_of_all_unsetset[0]
    for m in range(1, len(arr_of_unset)):
        p3 = p3 ^ arr_of_unset[m]

    for a in range(1, len(array_of_all_unsetset)):
        p4 = p4 ^ array_of_all_unsetset[a]

    second_missing_number = p3 ^ p4
    print(f"The Second missing number is: {second_missing_number}")
    
    
if __name__ == "__main__":
    # The Given Array
    arr = [1,2,3,4,5,6,8,9,10,12,13,14,15]
    length = len(arr)
    actual_length = 15
    find_missing_number(arr, length, actual_length)

Output

The First missing number is: 7
The Second missing number is: 11