Find missing elements of a range in Python
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