Recuento de números que faltan en una array ordenada

Dada una array ordenada arr[], la tarea es calcular la cantidad de números que faltan entre el primer y el último elemento de la array ordenada .

Ejemplos:

Entrada: arr[] = { 1, 4, 5, 8 }
Salida: 4
Explicación:
Los enteros que faltan en la array son {2, 3, 6, 7}.
Por lo tanto, la cuenta es 4.

Entrada: arr[] = {5, 10, 20, 40}
Salida: 32

Enfoque ingenuo:
el enfoque más simple para resolver el problema es iterar a través de la array y calcular la suma de todas las diferencias adyacentes de los elementos de la array .

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente:
para optimizar el enfoque anterior, la idea es observar que el recuento total de números en el rango de [arr[0], arr[N – 1]] está dado por arr[N-1] – arr[0 ] + 1 . Dado que el tamaño de la array es N , el número de enteros que faltan en la array viene dado por arr[N-1] – arr[0] + 1 – N .

A continuación se muestra la implementación del enfoque anterior:

// 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 Code 
int main() 
{ 
    int arr[] = { 5, 10, 20, 40 }; 
  
    int N = sizeof(arr) / sizeof(arr[0]); 
  
    countMissingNum(arr, N); 
  
    return 0; 
}

// Java program for the above approach 
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; 
  
    System.out.println(count); 
} 
  
// Driver code 
public 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 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 Code 
arr = [ 5, 10, 20, 40 ] 
  
N = len(arr) 
  
countMissingNum(arr, N) 
  
# This code is contributed by sanjoy_62

// C# program for the above approach 
using 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 code
public 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

32

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)