Dada una array de enteros únicos donde cada entero de la array dada se encuentra en el rango [1, N]. El tamaño de la array es (N-4). No se repite ningún elemento único. Por lo tanto, faltan cuatro números del 1 al N en la array. Encuentra los 4 números que faltan en orden ordenado.
Ejemplos:
Input : arr[] = {2, 5, 6, 3, 9}
Output : 1 4 7 8
Input : arr[] = {1, 7, 3, 13, 5, 10, 8, 4, 9}
Output : 2 6 11 12
Una solución O(N) simple es usar una array auxiliar de tamaño N para marcar los elementos visitados. Atraviese la array de entrada y marque elementos en la array auxiliar. Finalmente imprima todos aquellos índices que no estén marcados.
¿Cómo resolver con O (1) espacio auxiliar?
Inicializamos una array llamada ayudante de longitud 4 para compensar los 4 números faltantes y llenarlos con cero. Luego iteramos de i=0 a i < length_of_array de la array dada y tomamos el Absoluto del i-ésimo elemento y lo almacenamos en una variable llamada temp .
Ahora comprobaremos:
- Si el valor absoluto del elemento es menor que la longitud de la array de entrada, multiplicaremos el elemento array[temp] por -1 (para marcar el elemento visitado).
- Si el valor absoluto del elemento es mayor que la longitud de la array de entrada, pondremos el valor del elemento helper[temp%array.length] con -1 (para marcar el elemento visitado).
Luego, iteramos sobre la array de entrada y aquellos índices cuyo valor aún es mayor que cero, entonces esos elementos no se encontraron en la array de entrada. Entonces imprimimos el valor (índice+1) del índice cuyo elemento es mayor que cero.
Luego, iteraremos sobre la array de ayuda y aquellos índices cuyo valor aún sea mayor que cero, entonces esos elementos no se encontraron en la array de entrada. Entonces imprimimos el valor (index+array.length+1) del índice cuyo elemento es mayor que cero.
Implementación:
C++
// CPP program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
#include <bits/stdc++.h>
using namespace std;
// Finds missing 4 numbers in O(N) time
// and O(1) auxiliary space.
void missing4(int arr[], int n)
{
// To keep track of 4 possible numbers
// greater than length of input array
// In Java, helper is automatically
// initialized as 0.
int helper[4];
// Traverse the input array and mark
// visited elements either by marking
// them as negative in arr[] or in
// helper[].
for (int i = 0; i < n; i++) {
int temp = abs(arr[i]);
// If element is smaller than or
// equal to length, mark its
// presence in arr[]
if (temp <= n)
arr[temp - 1] *= (-1);
// Mark presence in helper[]
else if (temp > n) {
if (temp % n != 0)
helper[temp % n - 1] = -1;
else
helper[(temp % n) + n - 1] = -1;
}
}
// Print all those elements whose presence
// is not marked.
for (int i = 0; i < n; i++)
if (arr[i] > 0)
cout << (i + 1) << " ";
for (int i = 0; i < 4; i++)
if (helper[i] >= 0)
cout << (n + i + 1) << " ";
return;
}
// Driver code
int main()
{
int arr[] = { 1, 7, 3, 12, 5, 10, 8, 4, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
missing4(arr, n);
return 0;
}
// This code is contributed by Nikita Tiwari.
Java
// Java program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
class Missing4 {
// Finds missing 4 numbers in O(N) time
// and O(1) auxiliary space.
public static void missing4(int[] arr)
{
// To keep track of 4 possible numbers
// greater than length of input array
// In Java, helper is automatically
// initialized as 0.
int[] helper = new int[4];
// Traverse the input array and mark
// visited elements either by marking
// them as negative in arr[] or in
// helper[].
for (int i = 0; i < arr.length; i++) {
int temp = Math.abs(arr[i]);
// If element is smaller than or
// equal to length, mark its
// presence in arr[]
if (temp <= arr.length)
arr[temp - 1] *= (-1);
// Mark presence in helper[]
else if (temp > arr.length) {
if (temp % arr.length != 0)
helper[temp % arr.length - 1] = -1;
else
helper[(temp % arr.length) +
arr.length - 1] = -1;
}
}
// Print all those elements whose presence
// is not marked.
for (int i = 0; i < arr.length; i++)
if (arr[i] > 0)
System.out.print(i + 1 + " ");
for (int i = 0; i < helper.length; i++)
if (helper[i] >= 0)
System.out.print(arr.length + i + 1 + " ");
return;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 7, 3, 12, 5, 10, 8, 4, 9 };
missing4(arr);
}
}
Python3
# Python 3 program to find missing 4 elements # in an array of size N where elements are # in range from 1 to N+4. # Finds missing 4 numbers in O(N) time # and O(1) auxiliary space. def missing4( arr) : # To keep track of 4 possible numbers # greater than length of input array # In Java, helper is automatically # initialized as 0. helper = [0]*4 # Traverse the input array and mark # visited elements either by marking # them as negative in arr[] or in # helper[]. for i in range(0,len(arr)) : temp = abs(arr[i]) # If element is smaller than or # equal to length, mark its # presence in arr[] if (temp <= len(arr)) : arr[temp - 1] = arr[temp - 1] * (-1) # Mark presence in helper[] elif (temp > len(arr)) : if (temp % len(arr)) : helper[temp % len(arr) - 1] = -1 else : helper[(temp % len(arr)) +len(arr) - 1] = -1 # Print all those elements whose presence # is not marked. for i in range(0, len(arr) ) : if (arr[i] > 0) : print((i + 1) , end=" ") for i in range(0, len(helper)) : if (helper[i] >= 0) : print((len(arr) + i + 1) , end=" ") # Driver code arr = [ 1, 7, 3, 12, 5, 10, 8, 4, 9 ] missing4(arr) # This code is contributed # by Nikita Tiwari.
C#
// C# program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
using System;
class Missing4 {
// Finds missing 4 numbers in O(N) time
// and O(1) auxiliary space.
public static void missing4(int[] arr)
{
// To keep track of 4 possible numbers
// greater than length of input array
// In Java, helper is automatically
// initialized as 0.
int[] helper = new int[4];
// Traverse the input array and mark
// visited elements either by marking
// them as negative in arr[] or in
// helper[].
for (int i = 0; i < arr.Length; i++) {
int temp = Math.Abs(arr[i]);
// If element is smaller than or
// equal to length, mark its
// presence in arr[]
if (temp <= arr.Length)
arr[temp - 1] *= (-1);
// Mark presence in helper[]
else if (temp > arr.Length) {
if (temp % arr.Length != 0)
helper[temp % arr.Length - 1] = -1;
else
helper[(temp % arr.Length) +
arr.Length - 1] = -1;
}
}
// Print all those elements whose presence
// is not marked.
for (int i = 0; i < arr.Length; i++)
if (arr[i] > 0)
Console.Write(i + 1 + " ");
for (int i = 0; i < helper.Length; i++)
if (helper[i] >= 0)
Console.Write(arr.Length + i + 1 + " ");
return;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 7, 3, 12, 5, 10, 8, 4, 9 };
missing4(arr);
}
}
//This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to find missing 4 elements
// in an array of size N where elements
// are in range from 1 to N+4.
// Finds missing 4 numbers in O(N) time
// and O(1) auxiliary space.
function missing4($arr, $n)
{
// To keep track of 4 possible numbers
// greater than length of input array
// initialized as 0.
$helper = array(0, 0, 0, 0);
// Traverse the input array and mark
// visited elements either by marking
// them as negative in arr[] or in
// helper[].
for ($i = 0; $i < $n; $i++)
{
$temp = abs($arr[$i]);
// If element is smaller than or
// equal to length, mark its
// presence in arr[]
if ($temp <= $n)
$arr[$temp - 1] = $arr[$temp - 1] * (-1);
// Mark presence in helper[]
else if ($temp > $n)
{
if ($temp % $n != 0)
$helper[$temp % $n - 1] = -1;
else
$helper[($temp % $n) + $n - 1] = -1;
}
}
// Print all those elements whose
// presence is not marked.
for ($i = 0; $i < $n; $i++)
if ($arr[$i] > 0)
{
$a = $i + 1;
echo "$a", " ";
}
for ($i = 0; $i < 4; $i++)
if ($helper[$i] >= 0)
{
$b = $n + $i + 1;
echo "$b", " ";
}
echo "\n";
return;
}
// Driver code
$arr = array(1, 7, 3, 12, 5, 10, 8, 4, 9);
$n = sizeof($arr);
missing4($arr, $n);
// This code is contributed by iAyushRaj
?>
Javascript
<script>
// Javascript program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
// Finds missing 4 numbers in O(N) time
// and O(1) auxiliary space.
function missing4(arr)
{
// To keep track of 4 possible numbers
// greater than length of input array
// In Java, helper is automatically
// initialized as 0.
let helper =[];
for(let i = 0; i < 4; i++)
{
helper[i] = 0;
}
// Traverse the input array and mark
// visited elements either by marking
// them as negative in arr[] or in
// helper[].
for(let i = 0; i < arr.length; i++)
{
let temp = Math.abs(arr[i]);
// If element is smaller than or
// equal to length, mark its
// presence in arr[]
if (temp <= arr.length)
arr[temp - 1] = Math.floor(arr[temp - 1] * (-1));
// Mark presence in helper[]
else if (temp > arr.length)
{
if (temp % arr.length != 0)
helper[temp % arr.length - 1] = -1;
else
helper[(temp % arr.length) +
arr.length - 1] = -1;
}
}
// Print all those elements whose presence
// is not marked.
for(let i = 0; i < arr.length; i++)
if (arr[i] > 0)
document.write(i + 1 + " ");
for(let i = 0; i < helper.length; i++)
if (helper[i] >= 0)
document.write(arr.length + i + 1 + " ");
return;
}
// Driver code
let arr = [ 1, 7, 3, 12, 5, 10, 8, 4, 9 ];
missing4(arr);
// This code is contributed by susmitakundugoaldanga
</script>
Producción
2 6 11 13
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Este artículo es una contribución de Sanket Singh 2 . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA