Dada una array de n enteros únicos donde cada elemento de la array está en el rango [1, n]. La array tiene todos los elementos distintos y el tamaño de la array es (n-2). Por lo tanto, faltan dos números del rango en esta array. Encuentra los dos números que faltan.
Ejemplos:
Input : arr[] = {1, 3, 5, 6}
Output : 2 4
Input : arr[] = {1, 2, 4}
Output : 3 5
Input : arr[] = {1, 2}
Output : 3 4
Método 1: complejidad temporal O(n) y espacio adicional O(n)
Paso 1: Tome una marca de array booleana que realice un seguimiento de todos los elementos presentes en la array.
Paso 2: iterar de 1 a n, verificar cada elemento si está marcado como verdadero en la array booleana, si no, simplemente muestra ese elemento.
C++
// C++ Program to find two Missing Numbers using O(n)
// extra space
#include <bits/stdc++.h>
using namespace std;
// Function to find two missing numbers in range
// [1, n]. This function assumes that size of array
// is n-2 and all array elements are distinct
void findTwoMissingNumbers(int arr[], int n)
{
// Create a boolean vector of size n+1 and
// mark all present elements of arr[] in it.
vector<bool> mark(n+1, false);
for (int i = 0; i < n-2; i++)
mark[arr[i]] = true;
// Print two unmarked elements
cout << "Two Missing Numbers are\n";
for (int i = 1; i <= n; i++)
if (! mark[i])
cout << i << " ";
cout << endl;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 3, 5, 6};
// Range of numbers is 2 plus size of array
int n = 2 + sizeof(arr)/sizeof(arr[0]);
findTwoMissingNumbers(arr, n);
return 0;
}
Java
// Java Program to find two Missing Numbers using O(n)
// extra space
import java.util.*;
class GFG
{
// Function to find two missing numbers in range
// [1, n]. This function assumes that size of array
// is n-2 and all array elements are distinct
static void findTwoMissingNumbers(int arr[], int n)
{
// Create a boolean vector of size n+1 and
// mark all present elements of arr[] in it.
boolean []mark = new boolean[n+1];
for (int i = 0; i < n-2; i++)
mark[arr[i]] = true;
// Print two unmarked elements
System.out.println("Two Missing Numbers are");
for (int i = 1; i <= n; i++)
if (! mark[i])
System.out.print(i + " ");
System.out.println();
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 3, 5, 6};
// Range of numbers is 2 plus size of array
int n = 2 + arr.length;
findTwoMissingNumbers(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find two Missing Numbers using O(n)
# extra space
# Function to find two missing numbers in range
# [1, n]. This function assumes that size of array
# is n-2 and all array elements are distinct
def findTwoMissingNumbers(arr, n):
# Create a boolean vector of size n+1 and
# mark all present elements of arr[] in it.
mark = [False for i in range(n+1)]
for i in range(0,n-2,1):
mark[arr[i]] = True
# Print two unmarked elements
print("Two Missing Numbers are")
for i in range(1,n+1,1):
if (mark[i] == False):
print(i,end = " ")
print("\n")
# Driver program to test above function
if __name__ == '__main__':
arr = [1, 3, 5, 6]
# Range of numbers is 2 plus size of array
n = 2 + len(arr)
findTwoMissingNumbers(arr, n);
# This code is contributed by
# Surendra_Gangwar
C#
// C# Program to find two Missing Numbers
// using O(n) extra space
using System;
using System.Collections.Generic;
class GFG
{
// Function to find two missing numbers in range
// [1, n]. This function assumes that size of array
// is n-2 and all array elements are distinct
static void findTwoMissingNumbers(int []arr, int n)
{
// Create a boolean vector of size n+1 and
// mark all present elements of arr[] in it.
Boolean []mark = new Boolean[n + 1];
for (int i = 0; i < n - 2; i++)
mark[arr[i]] = true;
// Print two unmarked elements
Console.WriteLine("Two Missing Numbers are");
for (int i = 1; i <= n; i++)
if (! mark[i])
Console.Write(i + " ");
Console.WriteLine();
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 3, 5, 6};
// Range of numbers is 2 plus size of array
int n = 2 + arr.Length;
findTwoMissingNumbers(arr, n);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript Program to find two
// Missing Numbers using O(n) extra space
// Function to find two missing numbers in range
// [1, n]. This function assumes that size of array
// is n-2 and all array elements are distinct
function findTwoMissingNumbers(arr, n)
{
// Create a boolean vector of size n+1 and
// mark all present elements of arr[] in it.
let mark = new Array(n+1);
for (let i = 0; i < n-2; i++)
mark[arr[i]] = true;
// Print two unmarked elements
document.write("Two Missing Numbers are" + "</br>");
for (let i = 1; i <= n; i++)
if (!mark[i])
document.write(i + " ");
document.write("</br>");
}
let arr = [1, 3, 5, 6];
// Range of numbers is 2 plus size of array
let n = 2 + arr.length;
findTwoMissingNumbers(arr, n);
</script>
Producción
Two Missing Numbers are 2 4
Método 2: complejidad temporal O(n) y espacio adicional O(1)
La idea se basa en esta popular solución para encontrar un número faltante. Extendemos la solución para que se impriman dos elementos que faltan.
Averigüemos la suma de 2 números que faltan:
arrSum => Sum of all elements in the array
sum (Sum of 2 missing numbers) = (Sum of integers from 1 to n) - arrSum
= ((n)*(n+1))/2 – arrSum
avg (Average of 2 missing numbers) = sum / 2;
- Uno de los números será menor o igual que el promedio , mientras que el otro será estrictamente mayor que el promedio . Dos números nunca pueden ser iguales ya que todos los números dados son distintos.
- Podemos encontrar el primer número que falta como una suma de números naturales de 1 a avg , es decir, avg*(avg+1)/2 menos la suma de los elementos del arreglo menores que avg
- Podemos encontrar el segundo número que falta restando el primer número que falta de la suma de los números que faltan
Considere un ejemplo para una mejor aclaración.
Input : 1 3 5 6, n = 6
Sum of missing integers = n*(n+1)/2 - (1+3+5+6) = 6.
Average of missing integers = 6/2 = 3.
Sum of array elements less than or equal to average = 1 + 3 = 4
Sum of natural numbers from 1 to avg = avg*(avg + 1)/2
= 3*4/2 = 6
First missing number = 6 - 4 = 2
Second missing number = Sum of missing integers-First missing number
Second missing number = 6-2= 4
A continuación se muestra la implementación de la idea anterior.
C++
// C++ Program to find 2 Missing Numbers using O(1)
// extra space
#include <iostream>
using namespace std;
// Returns the sum of the array
int getSum(int arr[],int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to find two missing numbers in range
// [1, n]. This function assumes that size of array
// is n-2 and all array elements are distinct
void findTwoMissingNumbers(int arr[],int n)
{
// Sum of 2 Missing Numbers
int sum = (n*(n + 1)) /2 - getSum(arr, n-2);
// Find average of two elements
int avg = (sum / 2);
// Find sum of elements smaller than average (avg)
// and sum of elements greater than average (avg)
int sumSmallerHalf = 0, sumGreaterHalf = 0;
for (int i = 0; i < n-2; i++)
{
if (arr[i] <= avg)
sumSmallerHalf += arr[i];
else
sumGreaterHalf += arr[i];
}
cout << "Two Missing Numbers are\n";
// The first (smaller) element = (sum of natural
// numbers upto avg) - (sum of array elements
// smaller than or equal to avg)
int totalSmallerHalf = (avg*(avg + 1)) / 2;
int smallerElement = totalSmallerHalf - sumSmallerHalf;
cout << smallerElement << " ";
// The second (larger) element = (sum of both
// the elements) - smaller element
cout << sum - smallerElement;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 3, 5, 6};
// Range of numbers is 2 plus size of array
int n = 2 + sizeof(arr)/sizeof(arr[0]);
findTwoMissingNumbers(arr, n);
return 0;
}
Java
// Java Program to find 2 Missing
// Numbers using O(1) extra space
import java.io.*;
class GFG
{
// Returns the sum of the array
static int getSum(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to find two missing
// numbers in range [1, n]. This
// function assumes that size of
// array is n-2 and all array
// elements are distinct
static void findTwoMissingNumbers(int arr[],
int n)
{
// Sum of 2 Missing Numbers
int sum = (n * (n + 1)) /
2 - getSum(arr, n - 2);
// Find average of two elements
int avg = (sum / 2);
// Find sum of elements smaller
// than average (avg) and sum of
// elements greater than average (avg)
int sumSmallerHalf = 0,
sumGreaterHalf = 0;
for (int i = 0; i < n - 2; i++)
{
if (arr[i] <= avg)
sumSmallerHalf += arr[i];
else
sumGreaterHalf += arr[i];
}
System.out.println("Two Missing " +
"Numbers are");
// The first (smaller) element =
// (sum of natural numbers upto
// avg) - (sum of array elements
// smaller than or equal to avg)
int totalSmallerHalf = (avg *
(avg + 1)) / 2;
System.out.println(totalSmallerHalf -
sumSmallerHalf);
// The first (smaller) element =
// (sum of natural numbers from
// avg+1 to n) - (sum of array
// elements greater than avg)
System.out.println(((n * (n + 1)) / 2 -
totalSmallerHalf) -
sumGreaterHalf);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {1, 3, 5, 6};
// Range of numbers is 2
// plus size of array
int n = 2 + arr.length;
findTwoMissingNumbers(arr, n);
}
}
// This code is contributed by aj_36
Python3
# Python Program to find 2 Missing
# Numbers using O(1) extra space
# Returns the sum of the array
def getSum(arr,n):
sum = 0;
for i in range(0, n):
sum += arr[i]
return sum
# Function to find two missing
# numbers in range [1, n]. This
# function assumes that size of
# array is n-2 and all array
# elements are distinct
def findTwoMissingNumbers(arr, n):
# Sum of 2 Missing Numbers
sum = ((n * (n + 1)) / 2 -
getSum(arr, n - 2));
#Find average of two elements
avg = (sum / 2);
# Find sum of elements smaller
# than average (avg) and sum
# of elements greater than
# average (avg)
sumSmallerHalf = 0
sumGreaterHalf = 0;
for i in range(0, n - 2):
if (arr[i] <= avg):
sumSmallerHalf += arr[i]
else:
sumGreaterHalf += arr[i]
print("Two Missing Numbers are")
# The first (smaller) element = (sum
# of natural numbers upto avg) - (sum
# of array elements smaller than or
# equal to avg)
totalSmallerHalf = (avg * (avg + 1)) / 2
print(str(totalSmallerHalf -
sumSmallerHalf) + " ")
# The first (smaller) element = (sum
# of natural numbers from avg+1 to n) -
# (sum of array elements greater than avg)
print(str(((n * (n + 1)) / 2 -
totalSmallerHalf) -
sumGreaterHalf))
# Driver Code
arr = [1, 3, 5, 6]
# Range of numbers is 2
# plus size of array
n = 2 + len(arr)
findTwoMissingNumbers(arr, n)
# This code is contributed
# by Yatin Gupta
C#
// C# Program to find 2 Missing
// Numbers using O(1) extra space
using System;
class GFG
{
// Returns the sum of the array
static int getSum(int []arr, int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to find two missing
// numbers in range [1, n]. This
// function assumes that size of
// array is n-2 and all array
// elements are distinct
static void findTwoMissingNumbers(int []arr,
int n)
{
// Sum of 2 Missing Numbers
int sum = (n * (n + 1)) / 2 -
getSum(arr, n - 2);
// Find average of two elements
int avg = (sum / 2);
// Find sum of elements smaller
// than average (avg) and sum of
// elements greater than average (avg)
int sumSmallerHalf = 0,
sumGreaterHalf = 0;
for (int i = 0; i < n - 2; i++)
{
if (arr[i] <= avg)
sumSmallerHalf += arr[i];
else
sumGreaterHalf += arr[i];
}
Console.WriteLine("Two Missing " +
"Numbers are ");
// The first (smaller) element =
// (sum of natural numbers upto
// avg) - (sum of array elements
// smaller than or equal to avg)
int totalSmallerHalf = (avg *
(avg + 1)) / 2;
Console.WriteLine(totalSmallerHalf -
sumSmallerHalf);
// The first (smaller) element =
// (sum of natural numbers from
// avg+1 to n) - (sum of array
// elements greater than avg)
Console.WriteLine(((n * (n + 1)) / 2 -
totalSmallerHalf) -
sumGreaterHalf);
}
// Driver Code
static public void Main ()
{
int []arr = {1, 3, 5, 6};
// Range of numbers is 2
// plus size of array
int n = 2 + arr.Length;
findTwoMissingNumbers(arr, n);
}
}
// This code is contributed by ajit
PHP
<?php
// PHP Program to find 2 Missing
// Numbers using O(1) extra space
// Returns the sum of the array
function getSum($arr, $n)
{
$sum = 0;
for ($i = 0; $i < $n; $i++)
$sum += $arr[$i];
return $sum;
}
// Function to find two missing
// numbers in range [1, n]. This
// function assumes that size of
// array is n-2 and all array
// elements are distinct
function findTwoMissingNumbers($arr, $n)
{
// Sum of 2 Missing Numbers
$sum = ($n * ($n + 1)) /2 -
getSum($arr, $n - 2);
// Find average of two elements
$avg = ($sum / 2);
// Find sum of elements smaller
// than average (avg) and sum of
// elements greater than average (avg)
$sumSmallerHalf = 0;
$sumGreaterHalf = 0;
for ($i = 0; $i < $n - 2; $i++)
{
if ($arr[$i] <= $avg)
$sumSmallerHalf += $arr[$i];
else
$sumGreaterHalf += $arr[$i];
}
echo "Two Missing Numbers are\n";
// The first (smaller) element =
// (sum of natural numbers upto avg) -
// (sum of array elements smaller
// than or equal to avg)
$totalSmallerHalf = ($avg * ($avg + 1)) / 2;
echo ($totalSmallerHalf -
$sumSmallerHalf) , " ";
// The first (smaller) element =
// (sum of natural numbers from avg +
// 1 to n) - (sum of array elements
// greater than avg)
echo ((($n * ($n + 1)) / 2 - $totalSmallerHalf) -
$sumGreaterHalf);
}
// Driver Code
$arr= array (1, 3, 5, 6);
// Range of numbers is
// 2 plus size of array
$n = 2 + sizeof($arr);
findTwoMissingNumbers($arr, $n);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript Program to find 2 Missing
// Numbers using O(1) extra space
// Returns the sum of the array
function getSum(arr, n)
{
let sum = 0;
for (let i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to find two missing
// numbers in range [1, n]. This
// function assumes that size of
// array is n-2 and all array
// elements are distinct
function findTwoMissingNumbers(arr, n)
{
// Sum of 2 Missing Numbers
let sum = (n * (n + 1)) / 2 -
getSum(arr, n - 2);
// Find average of two elements
let avg = (sum / 2);
// Find sum of elements smaller
// than average (avg) and sum of
// elements greater than average (avg)
let sumSmallerHalf = 0,
sumGreaterHalf = 0;
for (let i = 0; i < n - 2; i++)
{
if (arr[i] <= avg)
sumSmallerHalf += arr[i];
else
sumGreaterHalf += arr[i];
}
document.write(
"Two Missing " + "Numbers are " + "</br>"
);
// The first (smaller) element =
// (sum of natural numbers upto
// avg) - (sum of array elements
// smaller than or equal to avg)
let totalSmallerHalf = (avg * (avg + 1)) / 2;
document.write(
(totalSmallerHalf - sumSmallerHalf) + " "
);
// The first (smaller) element =
// (sum of natural numbers from
// avg+1 to n) - (sum of array
// elements greater than avg)
document.write(
((n * (n + 1)) / 2 - totalSmallerHalf) -
sumGreaterHalf + "</br>"
);
}
let arr = [1, 3, 5, 6];
// Range of numbers is 2
// plus size of array
let n = 2 + arr.length;
findTwoMissingNumbers(arr, n);
</script>
Producción
Two Missing Numbers are 2 4
Nota: Puede haber problemas de desbordamiento en la solución anterior.
En el conjunto 2 a continuación, se analiza otra solución que es O (n) tiempo, O (1) espacio y no causa problemas de desbordamiento.
Encuentra dos números que faltan | Conjunto 2 (solución basada en XOR)
Este artículo es una contribución de Chirag Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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