Elements to be added such that all elements of a range are present in an array

Solution

Let us have a look into the various approaches to solve this problem.

Approach using Sorting

This is gonna be our first solution for the problem elements to be added such that all elements of a range are present in an array. If they are not consecutive, then we will increment the count. Otherwise, we will end the loop. Let us have a look at its algorithm.

Algorithm

Step 1 - Start

Step 2 - Input the array 

Step 3 - Declare a count variable.

Step 4 - Sort the array.

Step 5 - Check whether the numbers are consecutive or not.

Step 6 - If not update the count

Step 7 - Exit if all numbers are consecutive.

Was it not a simple algorithm? Why don't you try to implement this on your own?

If you cannot, then don't worry. Given below is the implementation for this.

Code

//A program in C++ for the above problem statement
#include <bits/stdc++.h>
using namespace std;

//Creating a function for displaying the count of numbers required to be added.

int countnum(int a[], int b)
{
int count = 0;

// Sorting the array

sort(a, a + b);

// Checking whether elements are consecutive
// or not. If not, then increament the count

for (int i = 0; i < b - 1; i++)
if (a[i] != a[i+1] &&
a[i] != a[i + 1] - 1)
count += a[i + 1] - a[i] - 1;
return count;
}

// Drivers code for final execution 

int main()
{
int a[] = { 3, 5, 8, 6 };
int b = sizeof(a) / sizeof(a[0]);
cout <<"Numbers to be added is "<< countnum(a, b) << endl;
return 0;
}

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

Run Code

The Above program will give the following output.

Output

Time Complexity

The time complexity for the given solution is O(N log N) as we are performing sorting.

Where N is the number of elements.

Space Complexity

The space complexity will be O(1) as no extra space is used.

Let us now see the following method

Approach using Hashing

In this method of solving the problem of elements to be added such that all elements of a range are present in an array, we will maintain a hash of elements present in the array, and subsequently, we will store the maximum element and the minimum element and then will traverse through the minimum element to the max element. During the traversing, we will update the count if We will not find an element in the hash.

Let us see the algorithm.

Algorithm

Step 1 - Start

Step 2 - Maintain a hash of all elements in the array.

Step 3 - Traverses through the min element to the max element.

Step 4 - Update the count if the element is not found in the hash table.

Step 5 - Exit.

Let us now look at its code

Code

// A C++ program for the hashing method
#include <bits/stdc++.h>
using namespace std;

//Creating a  Function to count numbers that are to be added

int countnum(int a[], int n)
{
unordered_set<int> sett;
int count = 0, maxi = INT_MIN, mini = INT_MAX;

// Making a hash of elements
// and store the minimum and maximum element

for (int i = 0; i < n; i++) {
sett.insert(a[i]);
if (a[i] < mini)
mini = a[i];
if (a[i] > maxi)
maxi = a[i];
}

// Traversing all the elements from minimum
// to the maximum and count if it is not
// in the hash

for (int i = mini; i <= maxi; i++)
if (sett.find(a[i]) == sett.end())
count++;
return count;
}

// Drivers code for the execution

int main()
{
int a[] = { 3, 5, 8, 6 };
int n = sizeof(a) / sizeof(a[0]);
cout <<"The numbers which are to be added is "<< countnum(a, n) << endl;
return 0;
}

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

Run Code

Output

Time Complexity

The time complexity for the given solution is O(N + max - min + 1).

Where N is the number of elements, min is the minimum element in the array, and max is the maximum element in the array.

Space Complexity

The space complexity will be O(1) as no extra space is used.

That was all in this article. Let us see some of the faqs related to this.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What is Hashing?

Hashing is a technique of mapping key-value pairs in a hash table. It uses a hash function to map the values against the key, and the efficiency of mapping depends on the hash function.

What are the different operations in hash and their time complexity?

Operations like insertion and deletion in hashing have a time complexity of O(1), and traversal is of O(n).

What are the different sorting algorithms?

There are tens of sorting algorithms with different time and space complexity. Some main algorithms are: 

1. Bubble sort
2. Insertion sort
3. Quick sort
4. Merge sort
5. Selection sort
6. Heap sort
7. Radix sort
8. Bucket sort

Define merge sort, and what is the time complexity of merge sort?

Merge sort is a divide-and-conquer algorithm that is based on the idea of breaking down an array into numerous sub-arrays until each sub-arrays has only one element, then merging those sub-arrays into a sorted list.

What are the drawbacks of the bubble sort?

The drawbacks of bubble sort are that it is extremely sluggish, taking O(n^2) time in both worst and average cases, and if the code is not optimized, the loop will continue to execute even if the array is sorted. 

Conclusion

In this article, we have extensively discussed how to display the elements to be added such that all elements of a range are present in an array. We implemented it in C++ using two different approaches. We also used some examples to make it easier to understand. 

After reading about how to populate Inorder Successor for all nodes, are you not feeling excited to read/explore more articles on related topics? Don't worry. Coding ninjas has you covered. To learn more, see  How to Find all the Palindromic Partitions of a String, Rat In A Maze, Binary Subarrays with sum or Reduce Array Size to The Half. 

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!