Dada una array arr[] de n enteros distintos. Los elementos se colocan secuencialmente en orden ascendente y falta un elemento. La tarea es encontrar el elemento que falta.
Ejemplos:
Entrada: arr[] = {1, 2, 4, 5, 6, 7, 8, 9}
Salida: 3
Entrada: arr[] = {-4, -3, -1, 0, 1, 2}
Salida: -2
Entrada: arr[] = {1, 2, 3, 4}
Salida: -1
No falta ningún elemento.
Principios:
- Busque inconsistencias: idealmente, la diferencia entre cualquier elemento y su índice debe ser arr[0] para cada elemento.
Ejemplo ,
A[] = {1, 2, 3, 4, 5} -> Consistente
B[] = {101, 102, 103, 104} -> Consistente
C[] = {1, 2, 4, 5, 6 } -> Incoherente como C[2] – 2 != C[0] es decir, 4 – 2 != 1
- Encontrar inconsistencias ayuda a escanear solo la mitad de la array cada vez en O (logN).
Algoritmo
- Encuentra el elemento medio y verifica si es consistente.
- Si el elemento intermedio es coherente, compruebe si la diferencia entre el elemento intermedio y su siguiente elemento es mayor que 1, es decir, compruebe si arr[mid + 1] – arr[mid] > 1
- En caso afirmativo, entonces arr[mid] + 1 es el elemento que falta.
- De lo contrario, tenemos que escanear la mitad derecha del elemento del medio y saltar al paso 1.
- Si el elemento intermedio es inconsistente, verifique si la diferencia entre el elemento intermedio y su elemento anterior es mayor que 1, es decir, verifique si arr[mid] – arr[mid – 1] > 1
- En caso afirmativo, entonces arr[mid] – 1 es el elemento que falta.
- Si no es así, tenemos que escanear la array de la mitad izquierda del elemento central y saltar al paso 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the missing element
int findMissing(int arr[], int n)
{
int l = 0, h = n - 1;
int mid;
while (h > l)
{
mid = l + (h - l) / 2;
// Check if middle element is consistent
if (arr[mid] - mid == arr[0])
{
// No inconsistency till middle elements
// When missing element is just after
// the middle element
if (arr[mid + 1] - arr[mid] > 1)
return arr[mid] + 1;
else
{
// Move right
l = mid + 1;
}
}
else
{
// Inconsistency found
// When missing element is just before
// the middle element
if (arr[mid] - arr[mid - 1] > 1)
return arr[mid] - 1;
else
{
// Move left
h = mid - 1;
}
}
}
// No missing element found
return -1;
}
// Driver code
int main()
{
int arr[] = { -9, -8, -7, -5, -4, -3, -2, -1, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << (findMissing(arr, n));
}
// This code iscontributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
class GFG {
// Function to return the missing element
public static int findMissing(int arr[], int n)
{
int l = 0, h = n - 1;
int mid;
while (h > l) {
mid = l + (h - l) / 2;
// Check if middle element is consistent
if (arr[mid] - mid == arr[0]) {
// No inconsistency till middle elements
// When missing element is just after
// the middle element
if (arr[mid + 1] - arr[mid] > 1)
return arr[mid] + 1;
else {
// Move right
l = mid + 1;
}
}
else {
// Inconsistency found
// When missing element is just before
// the middle element
if (arr[mid] - arr[mid - 1] > 1)
return arr[mid] - 1;
else {
// Move left
h = mid - 1;
}
}
}
// No missing element found
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = { -9, -8, -7, -5, -4, -3, -2, -1, 0 };
int n = arr.length;
System.out.print(findMissing(arr, n));
}
}
Python3
# Python implementation of the approach # Function to return the missing element def findMissing(arr, n): l, h = 0, n - 1 mid = 0 while (h > l): mid = l + (h - l) // 2 # Check if middle element is consistent if (arr[mid] - mid == arr[0]): # No inconsistency till middle elements # When missing element is just after # the middle element if (arr[mid + 1] - arr[mid] > 1): return arr[mid] + 1 else: # Move right l = mid + 1 else: # Inconsistency found # When missing element is just before # the middle element if (arr[mid] - arr[mid - 1] > 1): return arr[mid] - 1 else: # Move left h = mid - 1 # No missing element found return -1 # Driver code arr = [-9, -8, -7, -5, -4, -3, -2, -1, 0 ] n = len(arr) print(findMissing(arr, n)) # This code is contributed # by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the missing element
public static int findMissing(int[] arr, int n)
{
int l = 0, h = n - 1;
int mid;
while (h > l)
{
mid = l + (h - l) / 2;
// Check if middle element is consistent
if (arr[mid] - mid == arr[0])
{
// No inconsistency till middle elements
// When missing element is just after
// the middle element
if (arr[mid + 1] - arr[mid] > 1)
return arr[mid] + 1;
else
{
// Move right
l = mid + 1;
}
}
else
{
// Inconsistency found
// When missing element is just before
// the middle element
if (arr[mid] - arr[mid - 1] > 1)
return arr[mid] - 1;
else
{
// Move left
h = mid - 1;
}
}
}
// No missing element found
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { -9, -8, -7, -5, -4, -3, -2, -1, 0 };
int n = arr.Length;
Console.WriteLine(findMissing(arr, n));
}
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP implementation of the approach
// Function to return the missing element
function findMissing($arr, $n)
{
$l = 0; $h = $n - 1;
while ($h > $l)
{
$mid = floor($l + ($h - $l) / 2);
// Check if middle element is consistent
if ($arr[$mid] - $mid == $arr[0])
{
// No inconsistency till middle elements
// When missing element is just after
// the middle element
if ($arr[$mid + 1] - $arr[$mid] > 1)
return $arr[$mid] + 1;
else
{
// Move right
$l = $mid + 1;
}
}
else
{
// Inconsistency found
// When missing element is just before
// the middle element
if ($arr[$mid] - $arr[$mid - 1] > 1)
return $arr[$mid] - 1;
else
{
// Move left
$h = $mid - 1;
}
}
}
// No missing element found
return -1;
}
// Driver code
$arr = array( -9, -8, -7, -5, -
4, -3, -2, -1, 0 );
$n = count($arr);
echo findMissing($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the missing element
function findMissing(arr, n)
{
let l = 0, h = n - 1;
let mid;
while (h > l)
{
mid = l + Math.floor((h - l) / 2);
// Check if middle element is consistent
if (arr[mid] - mid == arr[0])
{
// No inconsistency till middle elements
// When missing element is just after
// the middle element
if (arr[mid + 1] - arr[mid] > 1)
return arr[mid] + 1;
else
{
// Move right
l = mid + 1;
}
}
else
{
// Inconsistency found
// When missing element is just before
// the middle element
if (arr[mid] - arr[mid - 1] > 1)
return arr[mid] - 1;
else
{
// Move left
h = mid - 1;
}
}
}
// No missing element found
return -1;
}
// Driver code
let arr = [ -9, -8, -7, -5, -4, -3, -2, -1, 0 ];
let n = arr.length;
document.write(findMissing(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
-6
Complejidad de tiempo: O(log(N) )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Neelansh Gupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA