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):
- 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> |
2
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> |
5
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); |
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.
Contact Us