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>
Producción
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>
Producción
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>
Producción
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