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
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
- 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;
}
|
Java
import java.util.Arrays;
class GFG {
public static 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 );
}
}
System.out.println(count);
}
public static void main(String[] args) {
int [] arr = { 5 , 10 , 20 , 40 };
int N = arr.length;
countMissingNum(arr, N);
}
}
|
Python
def CountMissingNum(a, N):
count = 0
for i in range (N - 1 ):
if a[i + 1 ] ! = a[i] + 1 :
count + = (a[i + 1 ] - a[i] - 1 )
print (count)
arr = [ 5 , 10 , 20 , 40 ]
N = len (arr)
CountMissingNum(arr, N)
|
C#
using System;
class GFG
{
public static 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);
}
}
Console.WriteLine(count);
}
public static void Main( string [] args)
{
int [] arr = { 5, 10, 20, 40 };
int N = arr.Length;
CountMissingNum(arr, N);
}
}
|
Javascript
function CountMissingNum(a, N) {
let count = 0;
for (let i = 0; i < N - 1; i++) {
if (a[i + 1] !== a[i] + 1) {
count += (a[i + 1] - a[i] - 1);
}
}
console.log(count);
}
const arr = [5, 10, 20, 40];
const N = arr.length;
CountMissingNum(arr, N);
|
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++
#include <bits/stdc++.h>
using namespace std;
void countMissingNum( int a[], int N)
{
int count = a[N - 1] - a[0] + 1 - N;
cout << count << endl;
}
int main()
{
int arr[] = { 5, 10, 20, 40 };
int N = sizeof (arr) / sizeof (arr[0]);
countMissingNum(arr, N);
return 0;
}
|
Java
class GFG{
public static void countMissingNum( int [] a,
int N)
{
int count = a[N - 1 ] - a[ 0 ] + 1 - N;
System.out.println(count);
}
public static void main(String[] args)
{
int arr[] = { 5 , 10 , 20 , 40 };
int N = arr.length;
countMissingNum(arr, N);
}
}
|
Python3
def countMissingNum(a, N):
count = a[N - 1 ] - a[ 0 ] + 1 - N
print (count)
arr = [ 5 , 10 , 20 , 40 ]
N = len (arr)
countMissingNum(arr, N)
|
C#
using System;
class GFG{
public static void countMissingNum( int [] a,
int N)
{
int count = a[N - 1] - a[0] + 1 - N;
Console.Write(count);
}
public static void Main( string [] args)
{
int []arr = { 5, 10, 20, 40 };
int N = arr.Length;
countMissingNum(arr, N);
}
}
|
Javascript
function countMissingNum(a, N)
{
let count = a[N - 1] - a[0] + 1 - N;
console.log(count);
}
let arr = [ 5, 10, 20, 40 ];
let N = arr.length;
countMissingNum(arr, N);
|
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach : Using Hashing
- 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++
#include <iostream>
#include <unordered_set>
using namespace std;
int 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;
}
int 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 {
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;
}
public static void main(String[] args) {
int [] arr = { 5 , 10 , 20 , 40 };
int n = arr.length;
System.out.println(countMissingNumbers(arr, n));
}
}
|
Python3
def 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
if __name__ = = "__main__" :
arr = [ 5 , 10 , 20 , 40 ]
n = len (arr)
print (countMissingNumbers(arr))
|
C#
using System;
using System.Collections.Generic;
public class GFG
{
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;
}
public static void Main()
{
int [] arr = { 5, 10, 20, 40 };
int n = arr.Length;
Console.WriteLine(CountMissingNumbers(arr, n));
}
}
|
Javascript
function GFG(arr) {
const hashSet = new Set(arr);
const first = arr[0];
const last = arr[arr.length - 1];
let count = 0;
for (let i = first; i <= last; i++) {
if (!hashSet.has(i)) {
count++;
}
}
return count;
}
const arr = [5, 10, 20, 40];
console.log(GFG(arr));
|
Contact Us