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

Last Updated : 18 Sep, 2023

Given an array of size N. Let A and B be the minimum and maximum in the array respectively. Task is to find how many number should be added to the given array such that all the element in the range [A, B] occur at-least once in the array.
Examples:

Input : arr[] = {4, 5, 3, 8, 6}
Output : 1
Only 7 to be added in the list.

Input : arr[] = {2, 1, 3}
Output : 0

Method 1 (Sorting):

Sort the array.
Compare arr[i] == arr[i+1]-1 or not. If not, update count = arr[i+1]-arr[i]-1.
Return count.

Implementation:

C++

// C++ program for above implementation 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to count numbers to be added 
int countNum(int arr[], int n) 
{ 
    int count = 0; 
  
    // Sort the array 
    sort(arr, arr + n); 
  
    // Check if elements are consecutive 
    //  or not. If not, update count 
    for (int i = 0; i < n - 1; i++) 
        if (arr[i] != arr[i+1] &&  
            arr[i] != arr[i + 1] - 1) 
            count += arr[i + 1] - arr[i] - 1; 
  
    return count; 
} 
  
// Drivers code 
int main() 
{ 
    int arr[] = { 3, 5, 8, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << countNum(arr, n) << endl; 
    return 0; 
} 

Java

// java program for above implementation 
import java.io.*; 
import java.util.*; 
  
public class GFG { 
      
    // Function to count numbers to be added 
    static int countNum(int []arr, int n) 
    { 
        int count = 0; 
      
        // Sort the array 
        Arrays.sort(arr); 
      
        // Check if elements are consecutive 
        // or not. If not, update count 
        for (int i = 0; i < n - 1; i++) 
            if (arr[i] != arr[i+1] &&  
                arr[i] != arr[i + 1] - 1) 
                count += arr[i + 1] - arr[i] - 1; 
      
        return count; 
    } 
      
    // Drivers code 
    static public void main (String[] args) 
    { 
          
        int []arr = { 3, 5, 8, 6 }; 
        int n = arr.length; 
          
        System.out.println(countNum(arr, n)); 
    } 
} 
  
// This code is contributed by vt_m. 

Python3

# python program for above implementation 
  
# Function to count numbers to be added 
def countNum(arr, n):  
      
    count = 0
  
    # Sort the array 
    arr.sort() 
  
    # Check if elements are consecutive 
    # or not. If not, update count 
    for i in range(0, n-1): 
        if (arr[i] != arr[i+1] and
            arr[i] != arr[i + 1] - 1): 
            count += arr[i + 1] - arr[i] - 1; 
  
    return count 
  
# Drivers code 
arr = [ 3, 5, 8, 6 ] 
n = len(arr) 
print(countNum(arr, n)) 
  
# This code is contributed by Sam007 

C#

// C# program for above implementation 
using System; 
  
public class GFG { 
      
    // Function to count numbers to be added 
    static int countNum(int []arr, int n) 
    { 
        int count = 0; 
      
        // Sort the array 
        Array.Sort(arr); 
      
        // Check if elements are consecutive 
        // or not. If not, update count 
        for (int i = 0; i < n - 1; i++) 
            if (arr[i] != arr[i+1] &&  
                arr[i] != arr[i + 1] - 1) 
                count += arr[i + 1] - arr[i] - 1; 
      
        return count; 
    } 
      
    // Drivers code 
    static public void Main () 
    { 
          
        int []arr = { 3, 5, 8, 6 }; 
        int n = arr.Length; 
          
        Console.WriteLine(countNum(arr, n)); 
    } 
} 
  
// This code is contributed by vt_m. 

PHP

<?php 
// PHP program for  
// above implementation 
  
// Function to count  
// numbers to be added 
function countNum($arr, $n) 
{ 
  
    $count = 0; 
  
    // Sort the array 
    sort($arr); 
  
    // Check if elements are  
    // consecutive or not.  
    // If not, update count 
    for ($i = 0; $i < $n - 1; $i++) 
        if ($arr[$i] != $arr[$i + 1] &&  
            $arr[$i] != $arr[$i + 1] - 1) 
            $count += $arr[$i + 1] -  
                      $arr[$i] - 1; 
  
    return $count; 
} 
  
// Driver code 
$arr = array(3, 5, 8, 6); 
$n = count($arr); 
echo countNum($arr, $n) ; 
  
// This code is contributed 
// by anuj_67. 
?> 

Javascript

<script> 
// Javascript program for above implementation 
  
    // Function to count numbers to be added 
       function countNum(arr, n) 
    { 
        let count = 0; 
        
        // Sort the array 
        arr.sort(); 
        
        // Check if elements are consecutive 
        // or not. If not, update count 
        for (let i = 0; i < n - 1; i++) 
            if (arr[i] != arr[i+1] &&  
                arr[i] != arr[i + 1] - 1) 
                count += arr[i + 1] - arr[i] - 1; 
        
        return count; 
    } 
      
// Driver code 
        let arr = [ 3, 5, 8, 6 ]; 
        let n = arr.length; 
            
        document.write(countNum(arr, n)); 
        
      // This code is contributed by sanjoy_62. 
</script> 

Output

Time Complexity: O(n log n)
Auxiliary Space: O(1)

Method 2 (Use Hashing):

Maintain a hash of array elements.
Store minimum and maximum element.
Traverse from minimum to maximum element in hash
And count if element is not in hash.
Return count.

Implementation:

C++

// C++ program for above implementation 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to count numbers to be added 
int countNum(int arr[], int n) 
{ 
    unordered_set<int> s; 
    int count = 0, maxm = INT_MIN, minm = INT_MAX; 
  
    // Make a hash of elements 
    // and store minimum and maximum element 
    for (int i = 0; i < n; i++) { 
        s.insert(arr[i]); 
        if (arr[i] < minm) 
            minm = arr[i]; 
        if (arr[i] > maxm) 
            maxm = arr[i]; 
    } 
  
    // Traverse all elements from minimum 
    // to maximum and count if it is not 
    // in the hash 
    for (int i = minm; i <= maxm; i++) 
        if (s.find(arr[i]) == s.end()) 
            count++; 
    return count; 
} 
  
// Drivers code 
int main() 
{ 
    int arr[] = { 3, 5, 8, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << countNum(arr, n) << endl; 
    return 0; 
} 

Java

// Java implementation of the approach 
import java.util.HashSet; 
  
class GFG  
{ 
  
// Function to count numbers to be added 
static int countNum(int arr[], int n) 
{ 
    HashSet<Integer> s = new HashSet<>(); 
    int count = 0,  
        maxm = Integer.MIN_VALUE,  
        minm = Integer.MAX_VALUE; 
  
    // Make a hash of elements 
    // and store minimum and maximum element 
    for (int i = 0; i < n; i++)  
    { 
        s.add(arr[i]); 
        if (arr[i] < minm) 
            minm = arr[i]; 
        if (arr[i] > maxm) 
            maxm = arr[i]; 
    } 
  
    // Traverse all elements from minimum 
    // to maximum and count if it is not 
    // in the hash 
    for (int i = minm; i <= maxm; i++) 
        if (!s.contains(i)) 
            count++; 
    return count; 
} 
  
// Drivers code 
public static void main(String[] args)  
{ 
    int arr[] = { 3, 5, 8, 6 }; 
    int n = arr.length; 
    System.out.println(countNum(arr, n)); 
} 
} 
  
// This code is contributed by Rajput-Ji 

Python3

# Function to count numbers to be added 
def countNum(arr, n): 
  
    s = dict() 
    count, maxm, minm = 0, -10**9, 10**9
  
    # Make a hash of elements and store  
    # minimum and maximum element 
    for i in range(n): 
        s[arr[i]] = 1
        if (arr[i] < minm): 
            minm = arr[i] 
        if (arr[i] > maxm): 
            maxm = arr[i] 
      
    # Traverse all elements from minimum 
    # to maximum and count if it is not 
    # in the hash 
    for i in range(minm, maxm + 1): 
        if i not in s.keys(): 
            count += 1
    return count 
  
# Driver code 
arr = [3, 5, 8, 6 ] 
n = len(arr) 
print(countNum(arr, n)) 
      
# This code is contributed by mohit kumar 

C#

// C# implementation of the approach 
using System; 
using System.Collections.Generic; 
  
class GFG  
{ 
  
// Function to count numbers to be added 
static int countNum(int []arr, int n) 
{ 
    HashSet<int> s = new HashSet<int>(); 
    int count = 0,  
        maxm = int.MinValue,  
        minm = int.MaxValue; 
  
    // Make a hash of elements 
    // and store minimum and maximum element 
    for (int i = 0; i < n; i++)  
    { 
        s.Add(arr[i]); 
        if (arr[i] < minm) 
            minm = arr[i]; 
        if (arr[i] > maxm) 
            maxm = arr[i]; 
    } 
  
    // Traverse all elements from minimum 
    // to maximum and count if it is not 
    // in the hash 
    for (int i = minm; i <= maxm; i++) 
        if (!s.Contains(i)) 
            count++; 
    return count; 
} 
  
// Drivers code 
public static void Main(String[] args)  
{ 
    int []arr = { 3, 5, 8, 6 }; 
    int n = arr.Length; 
    Console.WriteLine(countNum(arr, n)); 
} 
} 
  
// This code is contributed by Rajput-Ji 

Javascript

<script> 
// Javascript implementation of the approach 
      
    // Function to count numbers to be added 
    function countNum(arr,n) 
    { 
        let s = new Set(); 
    let count = 0, 
        maxm = Number.MIN_VALUE, 
        minm = Number.MAX_VALUE; 
   
    // Make a hash of elements 
    // and store minimum and maximum element 
    for (let i = 0; i < n; i++) 
    { 
        s.add(arr[i]); 
        if (arr[i] < minm) 
            minm = arr[i]; 
        if (arr[i] > maxm) 
            maxm = arr[i]; 
    } 
   
    // Traverse all elements from minimum 
    // to maximum and count if it is not 
    // in the hash 
    for (let i = minm; i <= maxm; i++) 
        if (!s.has(i)) 
            count++; 
    return count; 
    } 
      
    // Drivers code 
    let arr=[3, 5, 8, 6 ]; 
    let n = arr.length; 
    document.write(countNum(arr, n)); 
      
      
  
// This code is contributed by unknown2108 
</script> 

Output

Time Complexity: O(n + max – min + 1)
Auxiliary Space: O(n), for use of set

Method 3 (Use Boolean array ):

We can initialize this array to all false.
Then, we can iterate through the input array and mark each number that falls within the range [A,B] as true in the boolean array.
we can count the number of false values in the boolean array, which will give us the number of missing numbers in the range [A,B].
This count will be the number of elements that we need to add to the input array to ensure that all numbers in the range [A,B] appear at least once.

C++

#include <iostream> 
#include <climits> // Required for INT_MAX and INT_MIN constants 
  
using namespace std; 
  
// Function to count the number of elements to add to the array 
int countToAdd(int arr[], int N) { 
    // Find the minimum and maximum values in the array 
    int A = INT_MAX, B = INT_MIN; 
    for (int i = 0; i < N; i++) { 
        A = min(A, arr[i]); 
        B = max(B, arr[i]); 
    } 
  
    // Create a boolean array called present to keep track of which elements are in the range 
    bool present[B - A + 1] = {false}; 
  
    // Loop over the input array, and set the corresponding element in the present array to true for each element 
    for (int i = 0; i < N; i++) { 
        if (!present[arr[i] - A]) { // Check if the element is in the range [A, B] 
            present[arr[i] - A] = true; 
        } 
    } 
  
    // Count the number of elements that are not yet present in the present array 
    int count = 0; 
    for (int i = A; i <= B; i++) { 
        if (!present[i - A]) { // Check if the element is in the range [A, B] 
            count++; 
        } 
    } 
  
    // Return the count 
    return count; 
} 
  
int main() { 
    int arr[] = {4, 7, 2, 8, 5}; 
    int N = sizeof(arr) / sizeof(arr[0]); 
  
    // Call the countToAdd function to find the number of elements to add to the array 
    int count = countToAdd(arr, N); 
  
    // Output the result 
    cout << "Number of elements to be added: " << count << endl; 
  
    return 0; 
} 

Java

import java.util.*; 
  
class Main { 
    // Function to count the number of elements to add to 
    // the array 
    static int countToAdd(int[] arr, int N) 
    { 
        // Find the minimum and maximum values in the array 
        int A = Integer.MAX_VALUE, B = Integer.MIN_VALUE; 
        for (int i = 0; i < N; i++) { 
            A = Math.min(A, arr[i]); 
            B = Math.max(B, arr[i]); 
        } 
  
        // Create a boolean array called present to keep 
        // track of which elements are in the range 
        boolean[] present = new boolean[B - A + 1]; 
  
        // Loop over the input array, and set the 
        // corresponding element in the present array to 
        // true for each element 
        for (int i = 0; i < N; i++) { 
            if (!present[arr[i] 
                         - A]) { // Check if the element is 
                                 // in the range [A, B] 
                present[arr[i] - A] = true; 
            } 
        } 
  
        // Count the number of elements that are not yet 
        // present in the present array 
        int count = 0; 
        for (int i = A; i <= B; i++) { 
            if (!present[i - A]) { // Check if the element 
                                   // is in the range [A, B] 
                count++; 
            } 
        } 
  
        // Return the count 
        return count; 
    } 
  
    public static void main(String[] args) 
    { 
        int[] arr = { 4, 7, 2, 8, 5 }; 
        int N = arr.length; 
  
        // Call the countToAdd function to find the number 
        // of elements to add to the array 
        int count = countToAdd(arr, N); 
  
        // Output the result 
        System.out.println( 
            "Number of elements to be added: " + count); 
    } 
}

Python3

import sys 
  
# Function to count the number of elements to add to the array 
  
  
def countToAdd(arr, N): 
    # Find the minimum and maximum values in the array 
    A = sys.maxsize 
    B = -sys.maxsize - 1
    for i in range(N): 
        A = min(A, arr[i]) 
        B = max(B, arr[i]) 
  
    # Create a boolean array called present to keep track of which elements are in the range 
    present = [False] * (B - A + 1) 
  
    # Loop over the input array, and set the corresponding element in the present array to true for each element 
    for i in range(N): 
        if not present[arr[i] - A]:  # Check if the element is in the range [A, B] 
            present[arr[i] - A] = True
  
    # Count the number of elements that are not yet present in the present array 
    count = 0
    for i in range(A, B + 1): 
        if not present[i - A]:  # Check if the element is in the range [A, B] 
            count += 1
  
    # Return the count 
    return count 
  
  
arr = [4, 7, 2, 8, 5] 
N = len(arr) 
  
# Call the countToAdd function to find the number of elements to add to the array 
count = countToAdd(arr, N) 
  
# Output the result 
print("Number of elements to be added:", count) 

C#

using System; 
  
class GFG { 
    // Function to count the number of elements to add to 
    // the array 
    static int countToAdd(int[] arr, int N) 
    { 
        // Find the minimum and maximum values in the array 
        int A = int.MaxValue, B = int.MinValue; 
        for (int i = 0; i < N; i++) { 
            A = Math.Min(A, arr[i]); 
            B = Math.Max(B, arr[i]); 
        } 
  
        // Create a boolean array called present to keep 
        // track of which elements are in the range 
        bool[] present = new bool[B - A + 1]; 
  
        // Loop over the input array, and set the 
        // corresponding element in the present array to 
        // true for each element 
        for (int i = 0; i < N; i++) { 
            if (!present[arr[i] 
                         - A]) // Check if the element is in 
                               // the range [A, B] 
            { 
                present[arr[i] - A] = true; 
            } 
        } 
  
        // Count the number of elements that are not yet 
        // present in the present array 
        int count = 0; 
        for (int i = A; i <= B; i++) { 
            if (!present[i - A]) // Check if the element is 
                                 // in the range [A, B] 
            { 
                count++; 
            } 
        } 
  
        // Return the count 
        return count; 
    } 
  
    static void Main() 
    { 
        int[] arr = { 4, 7, 2, 8, 5 }; 
        int N = arr.Length; 
  
        // Call the countToAdd function to find the number 
        // of elements to add to the array 
        int count = countToAdd(arr, N); 
  
        // Output the result 
        Console.WriteLine("Number of elements to be added: "
                          + count); 
    } 
}

Javascript

function countToAdd(arr, N) { 
  // Find the minimum and maximum values in the array 
  let A = Number.MAX_SAFE_INTEGER; 
  let B = Number.MIN_SAFE_INTEGER; 
  for (let i = 0; i < N; i++) { 
    A = Math.min(A, arr[i]); 
    B = Math.max(B, arr[i]); 
  } 
  
  // Create a boolean array called present to keep track of which elements are in the range 
  const present = new Array(B - A + 1).fill(false); 
  
  // Loop over the input array, and set the corresponding element in the present array to true for each element 
  for (let i = 0; i < N; i++) { 
    if (!present[arr[i] - A]) {  // Check if the element is in the range [A, B] 
      present[arr[i] - A] = true; 
    } 
  } 
  
  // Count the number of elements that are not yet present in the present array 
  let count = 0; 
  for (let i = A; i <= B; i++) { 
    if (!present[i - A]) {  // Check if the element is in the range [A, B] 
      count += 1; 
    } 
  } 
  
  // Return the count 
  return count; 
} 
  
const arr = [4, 7, 2, 8, 5]; 
const N = arr.length; 
  
// Call the countToAdd function to find the number of elements to add to the array 
const count = countToAdd(arr, N); 
  
// Output the result 
console.log("Number of elements to be added:", count); 

Output

Number of elements to be added: 2

Time Complexity: O(N + B – A), where N is the size of the input array and B – A is the size of the range [A, B]. The algorithm involves looping over the input array once to find the minimum and maximum values, and then looping over the range [A, B] to count the number of elements that are not present in the input array.

Auxiliary Space: O(B – A), as we are using a boolean array called present of size B – A + 1 to keep track of which elements are in the range [A, B]. This additional space is required to solve the problem without modifying the input array.

GeeksforGeeks

Improve

Range Queries for Frequencies of array elements

Cuckoo Hashing - Worst case O(1) Lookup!

Easy problems on Hashing

Intermediate problems on Hashing

Hard problems on Hashing

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

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?