Given a sorted array arr[], the task is to calculate the number of missing numbers between the first and last element of the sorted array.
Examples:
Input: arr[] = { 1, 4, 5, 8 } Output: 4 Explanation: The missing integers in the array are {2, 3, 6, 7}. Therefore, the count is 4. Input: arr[] = {5, 10, 20, 40} Output: 32
Naive Approach: The simplest approach to solve the problem is to iterate through the array and calculate the sum of all the adjacent differences of the elements of the array.
Step by step algorithm:
- Initialize a variable count to 0.
- Traverse the array from index 0 to N-2.
- If the difference between a[i+1] and a[i] is greater than 1, increment count by (a[i+1] – a[i] – 1).
- Print count as the number of missing elements in the array.
C++
#include <iostream>using namespace std;void countMissingNum(int a[], int N){ int count = 0; for (int i = 0; i < N - 1; i++) { if (a[i+1] != a[i] + 1) { count += (a[i+1] - a[i] - 1); } } cout << count << endl;}int main(){ int arr[] = { 5, 10, 20, 40 }; int N = sizeof(arr) / sizeof(arr[0]); countMissingNum(arr, N); return 0;}//This code is contributed by Zaid Khan |
Java
import java.util.Arrays;class GFG { // This function displays the count of the missing numbers public static void countMissingNum(int[] a, int N) { int count = 0; // Iterating over the array for (int i = 0; i < N - 1; i++) { // Checking if the consecutive number is not present if (a[i + 1] != a[i] + 1) { count += (a[i + 1] - a[i] - 1); } } System.out.println(count); } // Driver code public static void main(String[] args) { int[] arr = { 5, 10, 20, 40 }; int N = arr.length; // Function call countMissingNum(arr, N); }} |
Python
# This function displays the count of the missing numbersdef CountMissingNum(a, N): count = 0 # Iterating over the array for i in range(N - 1): # Checking if the consecutive number is not present if a[i + 1] != a[i] + 1: count += (a[i + 1] - a[i] - 1) print(count)# Driver codearr = [5, 10, 20, 40]N = len(arr)# Function callCountMissingNum(arr, N) |
C#
using System;class GFG{ // This function displays the count of the missing numbers public static void CountMissingNum(int[] a, int N) { int count = 0; // Iterating over the array for (int i = 0; i < N - 1; i++) { // Checking if the consecutive number is not present if (a[i + 1] != a[i] + 1) { count += (a[i + 1] - a[i] - 1); } } Console.WriteLine(count); } // Driver code public static void Main(string[] args) { int[] arr = { 5, 10, 20, 40 }; int N = arr.Length; // Function call CountMissingNum(arr, N); }} |
Javascript
// This function displays the count of the missing numbersfunction CountMissingNum(a, N) {let count = 0;// Iterating over the arrayfor (let i = 0; i < N - 1; i++) { // Checking if the consecutive number is not present if (a[i + 1] !== a[i] + 1) { count += (a[i + 1] - a[i] - 1); }}console.log(count);}// Driver codeconst arr = [5, 10, 20, 40];const N = arr.length;// Function callCountMissingNum(arr, N); |
Output
32
Time Complexity:O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to observe that the total count of numbers in the range of [arr[0], arr[N – 1]] is given by arr[N-1] – arr[0] + 1. Since the size of the array is N, the count of missing integers in the array is given by arr[N-1] – arr[0] + 1 – N. Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function that find the count of// missing numbers in array a[]void countMissingNum(int a[], int N){ // Calculate the count of missing // numbers in the array int count = a[N - 1] - a[0] + 1 - N; cout << count << endl;}// Driver Codeint main(){ int arr[] = { 5, 10, 20, 40 }; int N = sizeof(arr) / sizeof(arr[0]); countMissingNum(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function that find the count of// missing numbers in array a[]public static void countMissingNum(int[] a, int N){ // Calculate the count of missing // numbers in the array int count = a[N - 1] - a[0] + 1 - N; System.out.println(count);}// Driver codepublic static void main(String[] args){ int arr[] = { 5, 10, 20, 40 }; int N = arr.length; countMissingNum(arr, N);}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach# Function that find the count of# missing numbers in array a[]def countMissingNum(a, N): # Calculate the count of missing # numbers in the array count = a[N - 1] - a[0] + 1 - N print(count)# Driver Codearr = [ 5, 10, 20, 40 ]N = len(arr)countMissingNum(arr, N)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{ // Function that find the count of// missing numbers in array a[]public static void countMissingNum(int[] a, int N){ // Calculate the count of missing // numbers in the array int count = a[N - 1] - a[0] + 1 - N; Console.Write(count);}// Driver codepublic static void Main(string[] args){ int []arr = { 5, 10, 20, 40 }; int N = arr.Length; countMissingNum(arr, N);}}// This code is contributed by rutvik_56 |
Javascript
// JS Program for the above approach// Function that find the count of// missing numbers in array a[]function countMissingNum(a, N){ // Calculate the count of missing // numbers in the array let count = a[N - 1] - a[0] + 1 - N; console.log(count);}// Driver Codelet arr = [ 5, 10, 20, 40 ];let N = arr.length;countMissingNum(arr, N);// This code is contributed by phasing17 |
Output
32
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach : Using Hashing
Steps:
- First, create a hash table.
- Insert all the elements of the array into it.
- After inserted all elements, iterate over the range of values between the first and last element of the array.
- If an element is not present in the hash table, then it is a missing number.
- Keep track of the count of missing numbers and return it as output.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <iostream>#include <unordered_set>using namespace std;// Function to count the number of missing elements in a// sorted arrayint countMissingNumbers(int arr[], int n){ unordered_set<int> hashSet; for (int i = 0; i < n; i++) { hashSet.insert(arr[i]); } int first = arr[0]; int last = arr[n - 1]; int count = 0; for (int i = first; i <= last; i++) { if (hashSet.find(i) == hashSet.end()) { count++; } } return count;}// Driver Codeint main(){ int arr[] = { 5, 10, 20, 40 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countMissingNumbers(arr, n) << endl; return 0;} |
Java
import java.util.HashSet;class GFG { // Function to count the number of missing elements in a // sorted array public static int countMissingNumbers(int[] arr, int n) { HashSet<Integer> hashSet = new HashSet<Integer>(); for (int i = 0; i < n; i++) { hashSet.add(arr[i]); } int first = arr[0]; int last = arr[n - 1]; int count = 0; for (int i = first; i <= last; i++) { if (!hashSet.contains(i)) { count++; } } return count; } // Driver Code public static void main(String[] args) { int[] arr = { 5, 10, 20, 40 }; int n = arr.length; System.out.println(countMissingNumbers(arr, n)); }}// by phasing17 |
Python3
# Function to count the number of missing elements in a# sorted arraydef countMissingNumbers(arr): hashSet = set(arr) first = arr[0] last = arr[-1] count = 0 for i in range(first, last + 1): if i not in hashSet: count += 1 return count# Driver Codeif __name__ == "__main__": arr = [5, 10, 20, 40] n = len(arr) print(countMissingNumbers(arr)) |
C#
using System;using System.Collections.Generic;public class GFG{ // Function to count the number of missing elements in a // sorted array public static int CountMissingNumbers(int[] arr, int n) { HashSet<int> hashSet = new HashSet<int>(); for (int i = 0; i < n; i++) { hashSet.Add(arr[i]); } int first = arr[0]; int last = arr[n - 1]; int count = 0; for (int i = first; i <= last; i++) { if (!hashSet.Contains(i)) { count++; } } return count; } // Driver Code public static void Main() { int[] arr = { 5, 10, 20, 40 }; int n = arr.Length; Console.WriteLine(CountMissingNumbers(arr, n)); }}// by phasing17 |
Javascript
function GFG(arr) { // Create a Set to store the unique elements from // the input array const hashSet = new Set(arr); const first = arr[0]; const last = arr[arr.length - 1]; let count = 0; // Loop through the range of elements from // first to last for (let i = first; i <= last; i++) { if (!hashSet.has(i)) { count++; } } // Return the count of missing elements return count;}// Test the function with an example arrayconst arr = [5, 10, 20, 40];console.log(GFG(arr)); |
Output
32
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
