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

Problem Statement

“Elements to be added so that all elements of a range are present in array” states that you are given an array of integers. The problem statement asks to find out the count of elements to be added in an array so that all elements lie in the range [X, Y] inclusively at least once in an array. X and Y are the minimum and maximum numbers of an array respectively.

Example

arr[] = {4,5,7,9,11}

3

Explanation: X and Y are 4 and 11(minimum and maximum numbers respectively), within the range of these numbers, only 3 are missing 6, 8 and 10.

arr[] = {2,4,6,7}

2

Explanation: X and Y are 2 and 7(minimum and maximum numbers respectively), within the range of these numbers, only 2 are missing 3 and 5.

Algorithm to find Elements to be added so that all elements of a range are present in array

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

Explanation

We have an integer array. The problem is to find out the number of elements to be added in the array. So that all elements lie in the range of maximum and minimum numbers of an array so that no elements should occur at least once.

Declare a Set, Set has a property to store distinct elements only once. This means it removes the common elements and store only distinct elements. So we will be able to handle that case. Now we are going to insert all of the array elements into the set. Simultaneously we will find out the maximum and minimum element. So that we do not have to make an extra traversal to find out the max and min. After all, we just need to find out the count of missing elements within the range. So there is only a need to count the numbers. And we do not have to deal with the numbers themselves.

Now, we will be traversing the array starting from the minimum value in the array to the maximum value of an array. Because this is the only range we need. We will pick each of the numbers within the range and check if the set doesn’t have that range’s value. If the set doesn’t contain that current range value, then we are going to increase the count of output. And every time we will increase the value of output by 1 whenever we don’t have a range’s value present in the set. As if in the mentioned code minimum is 4 and maximum is 11 and in between that 6,8 and 10 are missing within the range (4,11), also these elements are not present in an array so will count that number of elements. And finally, we will return that output.

Code

C++ code to find elements to be added so that all elements of a range are present in array

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}

3

Java code to find Elements to be added so that all elements of a range are present in array

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}

3

Complexity Analysis

Time Complexity

O(max − min + 1) where “max” and “min” are the maximum and minimum value of the array. Since we traversed from minimum element to maximum element. That’s why in the worst case this value may exceed N elements. So, because max-min+1 may be bigger than N. The time complexity is O(max-min+1) where max denotes the maximum element, and min denotes the minimum element.

Space Complexity

O(N) where “N” is the number of elements in the array. Since we are storing only N elements the algorithm has linear space complexity.