Find missing elements of a range in Python

By Taanvi Goyal

In this simple tutorial, we are going to learn how to find missing elements of a range in Python programming with easy and simple code examples.

Suppose we have an array of any size and we have a range that has some elements range(start, end) and we have to check for all the numbers(elements) which are in the range but missing from the array, not present in the array.

When we find that missing number, we have to print them in a sorted way.

Example:

In: array[5] ={9,10,12,14,15}
  start = 9, end = 15
Out: Missing elements are : 11,13

 

We can solve this problem in the following two ways:

  • We can use the sorting
  • We can use hashing

As we know both Sorting and Hashing uses an array for their implementation. So, indirectly it will be solved by using the array.

Sorting

In this method, we first sort the array and then apply search operation to find the ‘start’, we start to traverse from start and it doesn’t find the element which is in the range but not in the array, it will keep printing it.

Below is our Python program that will find the missing elements of a range in the sorting method:

#first import the bisect library
import bisect 
def check_missing(array, n, start, end):       
    # First  Sort the input array 
    array.sort()    
    # Now perform binary search to find 'start'
    ptr = bisect.bisect_left(array,start) 
    index = ptr       
    # find from index and 
    # search every range element y after this
    ind = index 
    y= start
    while (ind < n and y <= end): 
    # if no match found 
    # print it  
        if(array[ind] != y): 
            print(y, end =" ")   
    # If  match found , move to next element in array[]  
        else: 
            ind = ind + 1
    # go to next element in range [start,end]  
        y = y + 1        
    while (y <= end):  
        print(y, end =" ") 
        y = y + 1
    
# Main
array = [1,2,4,6,8,9]  
n = len(array)
start = 1
end = 9
check_missing(array,n, start,end);

And below is the given output of the above program:

3 5 7
[Program finished]

 

Hashing

In this method, first, we have to create one hash table and every element of our array is inserted in it then we traverse the given range and it will print the missing elements.

Below is our code:

#Hash method to find missing element
def check_missing(array,n, start,end): 
  
    # Insert all elements of array[] in set  
    h = set(array)
  
    # Traverse the range  
    # print all the missing elements  
    for y in range(start,end + 1): 
        if y not in h: 
            print(y, end = ' ') 
  
# MainCode  
array= [1, 3, 5, 4] 
n = len(array) 
start  = 1
end= 9
check_missing(array,n, start, end)

And the output is given below:

2 6 7 8 9
[Program finished]

I hope you understood the topic. Try running the code, if you find any doubt you may drop a comment. Your feedback will be appreciated.

Leave a Reply