Tutorialspoint.dev

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

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)
1- Sort the array.
2- Compare arr[i] == arr[i+1]-1 or not. If not, update count = arr[i+1]-arr[i]-1.
3- Return count.

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.
?>

Output:

2

Time Complexity: O(n log n)

Method 2 (Use Hashing)
1- Maintain a hash of array elements.
2- Store minimm and maximum element.
3- Traverse from minimum to maximum element in hash
And count if element is not in hash.
4- Return count.

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;
}

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


Output:

2

Time Complexity- O(max – min + 1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter