Find Missing Elements of a Range

Code in CPP

/*
    C++ program to find missing elements of a range.
*/

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;

// Print all elements of range [lowervalue, highervalue] that are not present in arr[0..n-1].
void Missing_number(int arr[], int a, int lowervalue, int highervalue)
{
    // Insert all elements of arr[] in set
    unordered_set<int> x;
    for (int i = 0; i < a; i++)
        x.insert(arr[i]);

    // Traverse through the range a print all missing elements.
    for (int p = lowervalue ; p <= highervalue; p++)
        if (x.find(p) == x.end())
            cout << p << " ";
}

// Driver program
int main()
{
     int a;
     cout<<"Entre the size of array:\n";
     cin>>a;
     cout<<"Enter the elements:\n";
     int arr[a];
     for(int i=0;i<a;i++)
     {
         cin>>arr[i];
     }
     int lowervalue, highervalue;
     cout<<"Enter lower value:"\n;
     cin>>lowervalue;
     cout<<"Enter the higher value:\n";
     cin>>highervalue;
     cout<<"Missing elements are:\n";
     Missing_number(arr, a, lowervalue, highervalue);
     return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Code in Java

/*
    Java program to find missing elements of a range
*/

import java.util.HashSet;
import java.util.Scanner;
public class Main
{
   public static void MissingElements(int arr[], int lower, int higher)
   {
       HashSet<Integer> numberset = new HashSet<>();
       for (int i = 0; i < arr.length; i++)
       {
           numberset.add(arr[i]);
       }
       for (int i = lower; i <= higher; i++)
       {
           if (!numberset.contains(i))
           {
               System.out.print(i + " ");
           }
       }
   }
   
   public static void main(String[] args)
   {   
        int n;
        int [] given_arr;
        Scanner input = new Scanner(System.in);
        System.out.println("Enter the size of the arrray : \n");
        n = input.nextInt();
        given_arr = new int[n];
        System.out.println("Enter the input digits for array : \n");
        for(int i=0;i<n;i++)
        {
            int temp = input.nextInt();
            given_arr[i] = temp;
        }
        int lower, higher;
        System.out.println("Enter the lower value:\n");
        lower = input.nextInt();
        System.out.println("Enter the higher value:\n");
        higher = input.nextInt();
        MissingElements(given_arr, lower, higher);
   }
}

You can also try this code with Online Java Compiler

Run Code

Output

Code in Python

# A hashing-based Python3 program to find missing elements of a range in  an array

# Print all elements of range  [lower, higher] that are not present in arr[0..n-1]
def Missingnumber(arr, a, lower, higher):
    # Insert all elements of arr[] in set
    x = set(arr)
    # Traverse through the range
    # and print all missing elements
    print("Missing numbers are:")
    for p in range(lower, higher + 1):
        if p not in x:
            print(p, end=' ')
    return

# Driver Code
arr = []
a = int(input("Enter the length of array:"))
print("Enter the Elements of array:")
for x in range(0, a):
    z = int(input())
    arr.append(z)
    lower = int(input("Enter the lower value: "))
    higher = int(input("Enter the higher value: "))
    Missingnumber(arr, a, lower, higher)

You can also try this code with Online Python Compiler

Run Code

Output

Complexity Analysis

Time Complexity

O(n + (higher-lower+1)) where “n” is the number of elements present in the array, “high” and “low” is the input provided.

Space Complexity

O(n), in the worst case, if all elements are distinct. We’ll have to store all the elements. Thus making the algorithm requires linear time.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What are the advantages of using hash values?

When compared to other data structures, hashing offers a more flexible and secure way to retrieve data. Compared to searching for lists and arrays, it is faster.

What is the key in hashing?

The raw data to be hashed is the hashing key. The hashing algorithm is the function that performs to convert the hash key to the hash value. The hash value is the result of passing the hash key through the hashing algorithm.

What is the time complexity of hashing?

O(1) time

The required location is accessed in O(1) time complexity, and the hash key is calculated as usual in O(1) time complexity (1). In the ideal scenario, the element is directly inserted into the hash table because the key indicates a free space there. So, O is the overall complexity (1).

What are the problems with hashing?

• Table dimensions.
• The hash function.
• Collision resolution

In Python, how can I determine which elements are most frequent?

Use Python Counter, which provides a count for each element in a list. So, using the most common() method, we can easily identify the element that is used the most.

Conclusion

In this article, we have extensively discussed the problem to find missing element of a range in an array. We hope this blog has helped you understand this problem very well.

If you want to learn more about such problems, visit the given links below:

• Find three-element from different three arrays such that a + b + c = sum
• Distribute the maximum number of chocolates amongst X students
• Winner of Tic-tac-toe 
• Reduce array size to the half

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, Java Programming, and System Design, etc. Have a look at the interview experiences and interview bundle for placement preparations. And also, enroll in our courses and refer to the mock test and problems available.

Do upvote our blog to help other ninjas grow.

Happy Learning!