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.
leave a comment
0 Comments