Dada una array ordenada arr[] de N enteros, la tarea es encontrar los múltiples elementos que faltan en la array entre los rangos [arr[0], arr[N-1]] .
Ejemplos:
Entrada: arr[] = {6, 7, 10, 11, 13}
Salida: 8 9 12
Explicación:
Los elementos de la array están presentes en el rango del elemento de array máximo y mínimo [6, 13]. Por tanto, los valores totales serán {6, 7, 8, 9, 10, 11, 12, 13}.
Los elementos del rango anterior que faltan en la array son {8, 9, 12}.
Entrada: arr[] = {1, 2, 4, 6}
Salida: 3 5
Enfoque ingenuo: la idea ingenua es iterar sobre la diferencia entre el par de elementos consecutivos e imprimir todos los números en este rango si la diferencia no es cero. A continuación se muestran los pasos:
- Inicialice la variable diff que es igual a arr[0] – 0 .
- Ahora recorra la array y vea si la diferencia entre arr[i] – i y diff es cero o no.
- Si la diferencia no es igual a cero en los pasos anteriores, entonces se encuentra el elemento faltante.
- Para encontrar los múltiples elementos que faltan, ejecute un bucle dentro de él y vea si la diferencia es menor que arr[i]; luego imprimo el elemento que falta, es decir, i + diff .
- Ahora incremente la diferencia a medida que aumenta la diferencia ahora.
- Repita desde el paso 2 hasta que no se encuentren todos los números que faltan.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the missing elements void printMissingElements(int arr[], int N) { // Initialize diff int diff = arr[0] - 0; for (int i = 0; i < N; i++) { // Check if diff and arr[i]-i // both are equal or not if (arr[i] - i != diff) { // Loop for consecutive // missing elements while (diff < arr[i] - i) { cout << i + diff << " "; diff++; } } } } // Driver Code int main() { // Given array arr[] int arr[] = { 6, 7, 10, 11, 13 }; int N = sizeof(arr) / sizeof(int); // Function Call printMissingElements(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the missing elements static void printMissingElements(int arr[], int N) { // Initialize diff int diff = arr[0] - 0; for(int i = 0; i < N; i++) { // Check if diff and arr[i]-i // both are equal or not if (arr[i] - i != diff) { // Loop for consecutive // missing elements while (diff < arr[i] - i) { System.out.print((i + diff) + " "); diff++; } } } } // Driver Code public static void main (String[] args) { // Given array arr[] int arr[] = { 6, 7, 10, 11, 13 }; int N = arr.length; // Function call printMissingElements(arr, N); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the missing elements def printMissingElements(arr, N): # Initialize diff diff = arr[0] for i in range(N): # Check if diff and arr[i]-i # both are equal or not if(arr[i] - i != diff): # Loop for consecutive # missing elements while(diff < arr[i] - i): print(i + diff, end = " ") diff += 1 # Driver Code # Given array arr[] arr = [ 6, 7, 10, 11, 13 ] N = len(arr) # Function call printMissingElements(arr, N) # This code is contributed by Shivam Singh
C#
// C# program for the above approach using System; class GFG{ // Function to find the missing elements static void printMissingElements(int[] arr, int N) { // Initialize diff int diff = arr[0] - 0; for(int i = 0; i < N; i++) { // Check if diff and arr[i]-i // both are equal or not if (arr[i] - i != diff) { // Loop for consecutive // missing elements while (diff < arr[i] - i) { Console.Write(i + diff + " "); diff++; } } } } // Driver code static void Main() { // Given array arr[] int[] arr = { 6, 7, 10, 11, 13 }; int N = arr.Length; // Function call printMissingElements(arr, N); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> // Javascript program to gather characters // of a string in minimum cost // Function to find the missing elements function prletMissingElements(arr, N) { // Initialize diff let diff = arr[0] - 0; for(let i = 0; i < N; i++) { // Check if diff and arr[i]-i // both are equal or not if (arr[i] - i != diff) { // Loop for consecutive // missing elements while (diff < arr[i] - i) { document.write((i + diff) + " "); diff++; } } } } // Driver Code // Given array arr[] let arr = [ 6, 7, 10, 11, 13 ]; let N = arr.length; // Function call prletMissingElements(arr, N); </script>
8 9 12
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es utilizar Hashing para optimizar el enfoque anterior. Cree una array booleana (digamos b[] ) de tamaño igual al elemento máximo en la array y marque solo aquellas posiciones en la array b[] que están presentes en la array dada. Imprime todos los índices en la array b[] que no están marcados.
A continuación se muestran los pasos:
- Inicialice una array booleana b[] con cero de tamaño igual al elemento máximo de la array .
- Iterar sobre la array dada y marcar para cada elemento en la array dada marcar ese índice como verdadero en la array b[] .
- Ahora recorra la array dada b[] desde el índice arr[0] e imprima aquellos índices cuyo valor sea falso, ya que son el elemento que falta en la array dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the missing elements void printMissingElements(int arr[], int N) { // Initialize an array with zero // of size equals to the maximum // element in the array int b[arr[N - 1] + 1] = { 0 }; // Make b[i]=1 if i is present // in the array for (int i = 0; i < N; i++) { // If the element is present // make b[arr[i]]=1 b[arr[i]] = 1; } // Print the indices where b[i]=0 for (int i = arr[0]; i <= arr[N - 1]; i++) { if (b[i] == 0) { cout << i << " "; } } } // Driver Code int main() { // Given array arr[] int arr[] = { 6, 7, 10, 11, 13 }; int N = sizeof(arr) / sizeof(int); // Function Call printMissingElements(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the missing elements static void printMissingElements(int arr[], int N) { // Initialize an array with zero // of size equals to the maximum // element in the array int[] b = new int[arr[N - 1] + 1]; // Make b[i]=1 if i is present // in the array for(int i = 0; i < N; i++) { // If the element is present // make b[arr[i]]=1 b[arr[i]] = 1; } // Print the indices where b[i]=0 for(int i = arr[0]; i <= arr[N - 1]; i++) { if (b[i] == 0) { System.out.print(i + " "); } } } // Driver Code public static void main (String[] args) { // Given array arr[] int arr[] = { 6, 7, 10, 11, 13 }; int N = arr.length; // Function call printMissingElements(arr, N); } } // This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to find the missing elements def printMissingElements(arr, N): # Initialize an array with zero # of size equals to the maximum # element in the array b = [0] * (arr[N - 1] + 1) # Make b[i]=1 if i is present # in the array for i in range(N): # If the element is present # make b[arr[i]]=1 b[arr[i]] = 1 # Print the indices where b[i]=0 for i in range(arr[0], arr[N - 1] + 1): if(b[i] == 0): print(i, end = " ") # Driver Code # Given array arr[] arr = [ 6, 7, 10, 11, 13 ] N = len(arr) # Function call printMissingElements(arr, N) # This code is contributed by Shivam Singh
C#
// C# program for // the above approach using System; class GFG{ // Function to find the missing elements static void printMissingElements(int []arr, int N) { // Initialize an array with zero // of size equals to the maximum // element in the array int[] b = new int[arr[N - 1] + 1]; // Make b[i]=1 if i is present // in the array for(int i = 0; i < N; i++) { // If the element is present // make b[arr[i]]=1 b[arr[i]] = 1; } // Print the indices where b[i]=0 for(int i = arr[0]; i <= arr[N - 1]; i++) { if (b[i] == 0) { Console.Write(i + " "); } } } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = {6, 7, 10, 11, 13}; int N = arr.Length; // Function call printMissingElements(arr, N); } } // This code is contributed by Princi Singh
Javascript
<script> // JavaScript program for the above approach // Function to find the missing elements function printMissingElements(arr, N) { // Initialize an array with zero // of size equals to the maximum // element in the array let b = new Uint8Array(arr[N - 1] + 1); // Make b[i]=1 if i is present // in the array for (let i = 0; i < N; i++) { // If the element is present // make b[arr[i]]=1 b[arr[i]] = 1; } // Print the indices where b[i]=0 for (let i = arr[0]; i <= arr[N - 1]; i++) { if (b[i] == 0) { document.write( i + " "); } } } // Driver Code // Given array arr[] let arr = [ 6, 7, 10, 11, 13 ]; let N = arr.length; // Function Call printMissingElements(arr, N); //This code is contributed by Mayank Tyagi </script>
8 9 12
Complejidad temporal: O(M), donde M es el elemento máximo del arreglo.
Espacio Auxiliar: O(M)
Enfoque más eficiente y simple :
En el siguiente enfoque simple, creamos una variable (cnt) esta variable mantiene el seguimiento del elemento presente en la array
1. Necesitamos atravesar el arr[0] hasta el arr[N] para encontrar el número que falta entre ellos.
2. En el ciclo for si arr[cnt] coincide con el elemento actual, entonces no imprimimos ese elemento y lo omitimos porque está presente en la array
una vez que encontramos el elemento, incrementamos el cnt ++ para señalar el siguiente elemento en la array
3. En otra parte, simplemente imprimimos el elemento que no coincide o no está presente en la array
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the missing elements void printMissingElements(int arr[], int N) { int cnt = 0; for (int i = arr[0]; i <= arr[N - 1]; i++) { // Check if number is equal to the first element in // given array if array element match skip it increment for next element if (arr[cnt] == i) { // Increment the count to check next element cnt++; } else { // Print missing number cout << i << " "; } } } // Driver Code int main() { // Given array arr[] int arr[] = { 6, 7, 10, 11, 13 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call printMissingElements(arr, N); return 0; } //This code is contributed by Kuldeep Kushwaha
Java
//Java program for the above approach import java.io.*; class GFG { // Function to find the missing elements public static void printMissingElements(int arr[], int N) { int cnt = 0; for (int i = arr[0]; i <= arr[N - 1]; i++) { // Check if number is equal to the first element in // given array if array element match skip it increment for next element if (arr[cnt] == i) { // Increment the count to check next element cnt++; } else { // Print missing number System.out.print(i + " "); } } } // Driver Code public static void main (String[] args) { // Given array arr[] int arr[] = { 6, 7, 10, 11, 13 }; int N = arr.length; // Function Call printMissingElements(arr, N); } } // This code is contributed by Shubham Singh
Python3
# Python program for the above approach # Function to find the missing elements def printMissingElements(arr, N): cnt = 0 for i in range(arr[0], arr[N - 1]+1): # Check if number is equal to the first element in # given array if array element match skip it increment for next element if (arr[cnt] == i): # Increment the count to check next element cnt += 1 else: # Print missing number print(i , end = " ") # Driver Code # Given array arr[] arr = [ 6, 7, 10, 11, 13 ] N = len(arr) # Function Call printMissingElements(arr, N) # This code is contributed by Shubham Singh
C#
//C# program for the above approach using System; using System.Linq; public class GFG{ // Function to find the missing elements public static void printMissingElements(int[] arr, int N) { int cnt = 0; for (int i = arr[0]; i <= arr[N - 1]; i++) { // Check if number is equal to the first element in // given array if array element match skip it increment for next element if (arr[cnt] == i) { // Increment the count to check next element cnt++; } else { // Print missing number Console.Write(i + " "); } } } // Driver Code static public void Main () { // Given array arr[] int[] arr = { 6, 7, 10, 11, 13 }; int N = arr.Length; // Function Call printMissingElements(arr, N); } } // This code is contributed by Shubham Singh
Javascript
<script> // Javascript program for the above approach // Function to find the missing elements function printMissingElements(arr, N) { var cnt = 0; for (var i = arr[0]; i <= arr[N - 1]; i++) { // Check if number is equal to the first element in // given array if array element match skip it increment for next element if (arr[cnt] == i) { // Increment the count to check next element cnt++; } else { // Print missing number document.write(i + " "); } } } // Driver Code // Given array arr[] var arr = [ 6, 7, 10, 11, 13 ]; var N = arr.length; // Function Call printMissingElements(arr, N); // This code is contributed by Shubham Singh </script>
8 9 12
Complejidad temporal : O(N), donde N es el elemento máximo del arreglo.
Espacio auxiliar : O (1) Debido a este método, se guardará el desbordamiento de hash o espacio adicional.
Publicación traducida automáticamente
Artículo escrito por NANDINIJAIN y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA