Encuentre el número perdido

Dada una array arr[] de tamaño N-1 con enteros en el rango de [1, N] , la tarea es encontrar el número que falta entre los primeros N enteros.

Nota: No hay duplicados en la lista.

Ejemplos: 

Entrada: arr[] = {1, 2, 4, 6, 3, 7, 8}, N = 7
Salida: 5
Explicación: El número que falta entre 1 y 8 es 5

Entrada: arr[] = {1, 2, 3, 5}, N = 5
Salida: 4
Explicación: El número que falta entre 1 y 5 es 4

Enfoque 1 (usando la suma de los primeros N números naturales) : la idea detrás del enfoque es usar la suma de los primeros N números.

Encuentra la suma de los números en el rango [1, N] usando la fórmula N * (N+1)/2 . Ahora encuentre la suma de todos los elementos en la array y réstelo de la suma de los primeros N números naturales. Esto le dará el valor del elemento faltante.

Siga los pasos mencionados a continuación para implementar la idea:

• Calcula la suma de los primeros N números naturales como sumtotal= N*(N+1)/2 .
• Atraviesa la array de principio a fin.
  • Encuentre la suma de todos los elementos de la array.
• Imprima el número que falta como SumTotal – suma de la array

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to get the missing number
int getMissingNo(int a[], int n)
{
    // Given the range of elements
    // are 1 more then the size of array
    int N = n + 1;
   
    int total = (N) * (N + 1) / 2;
    for (int i = 0; i < n; i++)
        total -= a[i];
    return total;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    int miss = getMissingNo(arr, N);
    cout << miss;
    return 0;
}

#include <stdio.h>
 
// Function to find the missing number
int getMissingNo(int a[], int n)
{
    int i, total;
    total = (n + 1) * (n + 2) / 2;
    for (i = 0; i < n; i++)
        total -= a[i];
    return total;
}
 
// Driver code
void main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    int miss = getMissingNo(arr, N);
    printf("%d", miss);
}

// Java program to find missing Number
 
import java.util.*;
import java.util.Arrays;
 
class GFG {
 
    // Function to find the missing number
    public static int getMissingNo(int[] nums, int n)
    {
        int sum = ((n + 1) * (n + 2)) / 2;
        for (int i = 0; i < n; i++)
            sum -= nums[i];
        return sum;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = arr.length;
        System.out.println(getMissingNo(arr, N));
    }
}

# Function to find the missing element
def getMissingNo(arr, n):
    total = (n + 1)*(n + 2)/2
    sum_of_A = sum(arr)
    return total - sum_of_A
 
# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 5]
    N = len(arr)
     
    # Function call
    miss = getMissingNo(arr, N)
    print(miss)
     
# This code is contributed by Pratik Chhajer

// C# program to find missing Number
using System;
 
class GFG {
    // Function to find missing number
    static int getMissingNo(int[] a, int n)
    {
        int total = (n + 1) * (n + 2) / 2;
 
        for (int i = 0; i < n; i++)
            total -= a[i];
 
        return total;
    }
 
    /* program to test above function */
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = 4;
        int miss = getMissingNo(arr, N);
        Console.Write(miss);
    }
}
 
// This code is contributed by Sam007_

<?php
// PHP program to find
// the Missing Number
 
// getMissingNo takes array and
// size of array as arguments
function getMissingNo ($a, $n)
{
    $total = ($n + 1) * ($n + 2) / 2;
    for ( $i = 0; $i < $n; $i++)
        $total -= $a[$i];
    return $total;
}
 
// Driver Code
$arr = array(1, 2, 3, 5);
$N = 4;
$miss = getMissingNo($arr, $N);
echo($miss);
 
// This code is contributed by Ajit.
?>

<script>
  
    // Function to get the missing number
    function getMissingNo(a, n) {
  
        let total = Math.floor((n + 1) * (n + 2) / 2);
        for (let i = 0; i < n; i++)
            total -= a[i];
        return total;
    }
  
    // Driver Code
 
    let arr = [ 1, 2, 3, 5 ];
    let N = arr.length;
    let miss = getMissingNo(arr, N);
    document.write(miss);
 
// This code is contributed by Surbhi Tyagi
 
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Modificación para desbordamiento: el enfoque sigue siendo el mismo, pero puede haber un desbordamiento si N es grande. 

Para evitar el desbordamiento de enteros, elija un número del rango [1, N] y reste un número de la array dada (no reste el mismo número dos veces). De esta manera no habrá ningún desbordamiento de enteros.

Algoritmo: 

• Cree una variable suma = 1 que almacenará el número que falta y una variable de contador c = 2 .
• Atraviesa la array de principio a fin.
  • Actualice el valor de sum como sum = sum – array[i] + c e incremente c en 1 . Esto realiza la tarea mencionada en la idea anterior]
• Imprime el número que falta como una suma .

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to get the missing element
int getMissingNo(int a[], int n)
{
    int i, total = 1;
 
    for (i = 2; i <= (n + 1); i++) {
        total += i;
        total -= a[i - 2];
    }
    return total;
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    cout << getMissingNo(arr, N);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

#include <stdio.h>
 
// Function to get the missing element
int getMissingNo(int a[], int n)
{
    int i, total = 1;
 
    for (i = 2; i <= (n + 1); i++) {
        total += i;
        total -= a[i - 2];
    }
    return total;
}
 
// Driver code
void main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    printf("%d", getMissingNo(arr, N));
}
// This code is contributed by Aditya Kumar (adityakumar129)

// Java implementation
class GFG {
   
    // Function to get the missing number
    static int getMissingNo(int a[], int n)
    {
        int total = 1;
        for (int i = 2; i <= (n + 1); i++) {
            total += i;
            total -= a[i - 2];
        }
        return total;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = arr.length;
       
        // Function call
        System.out.println(getMissingNo(arr, N));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Function to get the missing number
def getMissingNo(a, n):
    i, total = 0, 1
 
    for i in range(2, n + 2):
        total += i
        total -= a[i - 2]
    return total
 
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 5]
    N = len(arr)
 
    # Function call
    print(getMissingNo(arr, N))
 
# This code is contributed by Mohit kumar

using System;
 
class GFG {
 
    // Function to find the missing number
    static int getMissingNo(int[] a, int n)
    {
        int i, total = 1;
 
        for (i = 2; i <= (n + 1); i++) {
            total += i;
            total -= a[i - 2];
        }
        return total;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = (arr.Length);
       
        // Function call
        Console.Write(getMissingNo(arr, N));
    }
}
// This code is contributed by SoumikMondal

<script>
 
// a represents the array
// n : Number of elements in array a
function getMissingNo(a, n)
{
    let i, total=1;
     
    for (i = 2; i<= (n+1); i++)
    {
        total += i;
        total -= a[i-2];
    }
    return total;
}
 
//Driver Program
    let arr = [1, 2, 3, 5];
    let N = arr.length;
     
    // Function call
    document.write(getMissingNo(arr, N));
 
 
//This code is contributed by Mayank Tyagi
 
</script>

4

Complejidad temporal: O(N). Solo se necesita un recorrido de la array.
Espacio Auxiliar: O(1). No se necesita espacio adicional

Enfoque 2 (usando operaciones binarias) : este método usa la técnica de XOR para resolver el problema.  

XOR tiene ciertas propiedades 

• Suponga que un ₁ ⊕ un ₂ ⊕ un ₃ ⊕ . . . ⊕ un norte ₌ un y un ₁ ⊕ un ₂ ⊕ un ₃ ⊕ . . . ⊕ un _n-1 = segundo
• Entonces a ⊕ b = a _n

Siga los pasos mencionados a continuación para implementar la idea:

• Crea dos variables a = 0 y b = 0
• Ejecute un bucle de i = 1 a N :
  • Para cada índice, actualice a como a = a ^ i
• Ahora recorra la array desde i = de principio a fin.
  • Para cada índice, actualice b como b = b ^ arr[i] .
• El número que falta es a ^ b .

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to get the missing number
int getMissingNo(int a[], int n)
{
    // For xor of all the elements in array
    int x1 = a[0];
 
    // For xor of all the elements from 1 to n+1
    int x2 = 1;
 
    for (int i = 1; i < n; i++)
        x1 = x1 ^ a[i];
 
    for (int i = 2; i <= n + 1; i++)
        x2 = x2 ^ i;
 
    return (x1 ^ x2);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    int miss = getMissingNo(arr, N);
    cout << miss;
    return 0;
}

#include <stdio.h>
 
// Function to find the missing number
int getMissingNo(int a[], int n)
{
    int i;
 
    // For xor of all the elements in array
    int x1 = a[0];
 
    // For xor of all the elements from 1 to n+1
    int x2 = 1;
 
    for (i = 1; i < n; i++)
        x1 = x1 ^ a[i];
 
    for (i = 2; i <= n + 1; i++)
        x2 = x2 ^ i;
 
    return (x1 ^ x2);
}
 
// Driver code
void main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    int miss = getMissingNo(arr, N);
    printf("%d", miss);
}

// Java program to find missing Number
// using xor
 
class Main {
 
    // Function to find missing number
    static int getMissingNo(int a[], int n)
    {
        int x1 = a[0];
        int x2 = 1;
 
        // For xor of all the elements in array
        for (int i = 1; i < n; i++)
            x1 = x1 ^ a[i];
 
        // For xor of all the elements from 1 to n+1
        for (int i = 2; i <= n + 1; i++)
            x2 = x2 ^ i;
 
        return (x1 ^ x2);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 5 };
        int N = arr.length;
 
        // Function call
        int miss = getMissingNo(arr, N);
        System.out.println(miss);
    }
}

# Python3 program to find
# the missing Number
# getMissingNo takes list as argument
 
 
def getMissingNo(a, n):
    x1 = a[0]
    x2 = 1
 
    for i in range(1, n):
        x1 = x1 ^ a[i]
 
    for i in range(2, n + 2):
        x2 = x2 ^ i
 
    return x1 ^ x2
 
 
# Driver program to test above function
if __name__ == '__main__':
 
    arr = [1, 2, 3, 5]
    N = len(arr)
 
    # Driver code
    miss = getMissingNo(arr, N)
    print(miss)
 
# This code is contributed by Yatin Gupta

// C# program to find missing Number
// using xor
using System;
 
class GFG {
    // Function to find missing number
    static int getMissingNo(int[] a, int n)
    {
        int x1 = a[0];
        int x2 = 1;
 
        // For xor of all the elements in array
        for (int i = 1; i < n; i++)
            x1 = x1 ^ a[i];
 
        // For xor of all the elements from 1 to n+1
        for (int i = 2; i <= n + 1; i++)
            x2 = x2 ^ i;
 
        return (x1 ^ x2);
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = 4;
       
        // Function call
        int miss = getMissingNo(arr, N);
        Console.Write(miss);
    }
}
 
// This code is contributed by Sam007_

<?php
// PHP program to find
// the Missing Number
// getMissingNo takes array and
// size of array as arguments
function getMissingNo($a, $n)
{
    // For xor of all the
    // elements in array
    $x1 = $a[0];
     
    // For xor of all the
    // elements from 1 to n + 1
    $x2 = 1;
     
    for ($i = 1; $i < $n; $i++)
        $x1 = $x1 ^ $a[$i];
             
    for ($i = 2; $i <= $n + 1; $i++)
        $x2 = $x2 ^ $i;    
     
    return ($x1 ^ $x2);
}
 
// Driver Code
$arr = array(1, 2, 3, 5);
$N = 4;
$miss = getMissingNo($arr, $N);
echo($miss);
 
// This code is contributed by Ajit.
?>

<script>
      // Function to get the missing number
      function getMissingNo(a, n)
      {
       
        // For xor of all the elements in array
        var x1 = a[0];
 
        // For xor of all the elements from 1 to n+1
        var x2 = 1;
        for (var i = 1; i < n; i++) x1 = x1 ^ a[i];
        for (var i = 2; i <= n + 1; i++) x2 = x2 ^ i;
 
        return x1 ^ x2;
      }
 
      // Driver Code
 
      var arr = [1, 2, 3, 5];
      var N = arr.length;
      var miss = getMissingNo(arr, N);
      document.write(miss);
       
      // This code is contributed by rdtank.
    </script>

4

Complejidad temporal: O(N) 
Espacio auxiliar: O(1) 

Enfoque 3 (usando la ordenación cíclica ): la idea detrás de esto es la siguiente:

Todos los números de array dados están ordenados y en el rango de 1 a n-1. Si el rango es de 1 a N, entonces el índice de cada elemento de la array será el mismo que (valor – 1).

Siga los siguientes pasos para implementar la idea:

• Utilice la ordenación cíclica para ordenar los elementos en tiempo lineal.
• Ahora recorra desde i = 0 hasta el final de la array:
  • Si arr[i] no es lo mismo que i+1 , entonces el elemento faltante es ( i+1 ).
• Si todos los elementos están presentes, N es el elemento que falta en el rango [1, N] .

A continuación se muestra la implementación del enfoque anterior.

// C++ program to find the missing Number\
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the missing number
int getMissingNo(int a[], int n)
{
    int i = 0;
    while (i < n) {
        int correct = a[i] - 1;
        if (a[i] < n && a[i] != a[correct]) {
            swap(a[i], a[correct]);
        }
        else {
            i++;
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (i != a[i] - 1) {
            return i + 1;
        }
    }
 
    return n;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    int miss = getMissingNo(arr, N);
    cout << (miss);
    return 0;
}

// java program to check missingNo
import java.util.*;
public class MissingNumber {
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = arr.length;
 
        // Function call
        int ans = getMissingNo(arr, N);
        System.out.println(ans);
    }
 
    // Function to find the missing number
    static int getMissingNo(int[] arr, int n)
    {
        int i = 0;
        while (i < n) {
            // as array is of 1 based indexing so the
            // correct position or index number of each
            // element is element-1 i.e. 1 will be at 0th
            // index similarly 2 correct index will 1 so
            // on...
            int correctpos = arr[i] - 1;
            if (arr[i] < n && arr[i] != arr[correctpos]) {
                // if array element should be lesser than
                // size and array element should not be at
                // its correct position then only swap with
                // its correct positioin or index value
                swap(arr, i, correctpos);
            }
            else {
                // if element is at its correct position
                // just increment i and check for remaining
                // array elements
                i++;
            }
        }
        // check for missing element by comparing elements
        // with their index values
        for (int index = 0; index < arr.length; index++) {
            if (arr[index] != index + 1) {
                return index + 1;
            }
        }
        return arr.length;
    }
 
    static void swap(int[] arr, int i, int correctpos)
    {
        // swap elements with their correct indexes
        int temp = arr[i];
        arr[i] = arr[correctpos];
        arr[correctpos] = temp;
    }
}
// this code is contributed by devendra solunke

# Python3 program to check missingNo
 
# Function to find the missing number
def getMissingNo(arr, n) :
    i = 0;
     
    while (i < n) :
        # as array is of 1 based indexing so the
        # correct position or index number of each
        # element is element-1 i.e. 1 will be at 0th
        # index similarly 2 correct index will 1 so
        # on...
        correctpos = arr[i] - 1;
        if (arr[i] < n and arr[i] != arr[correctpos]) :
            # if array element should be lesser than
            # size and array element should not be at
            # its correct position then only swap with
            # its correct position or index value
            arr[i],arr[correctpos] = arr[correctpos], arr[i]
 
        else :
            # if element is at its correct position
            # just increment i and check for remaining
            # array elements
            i += 1;
             
    # check for missing element by comparing elements with their index values
    for index in range(n) :
        if (arr[index] != index + 1) :
            return index + 1;
             
    return n;
 
# Driver code
if __name__ == "__main__" :
    arr = [ 1, 2, 3, 5 ];
    N = len(arr);
    print(getMissingNo(arr, N));
 
 
    # This Code is Contributed by AnkThon

// C# program to implement
// the above approach
using System;
class GFG {
 
    // Function to find the missing number
    static int getMissingNo(int[] arr, int n)
    {
        int i = 0;
        while (i < n) {
            // as array is of 1 based indexing so the
            // correct position or index number of each
            // element is element-1 i.e. 1 will be at 0th
            // index similarly 2 correct index will 1 so
            // on...
            int correctpos = arr[i] - 1;
            if (arr[i] < n && arr[i] != arr[correctpos]) {
                // if array element should be lesser than
                // size and array element should not be at
                // its correct position then only swap with
                // its correct positioin or index value
                swap(arr, i, correctpos);
            }
            else {
                // if element is at its correct position
                // just increment i and check for remaining
                // array elements
                i++;
            }
        }
        // check for missing element by comparing elements
        // with their index values
        for (int index = 0; index < n; index++) {
            if (arr[index] != index + 1) {
                return index + 1;
            }
        }
        return n;
    }
 
    static void swap(int[] arr, int i, int correctpos)
    {
        // swap elements with their correct indexes
        int temp = arr[i];
        arr[i] = arr[correctpos];
        arr[correctpos] = temp;
    }
   
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 4, 5, 6 };
        int N = arr.Length;
       
        // Function call
        int ans = getMissingNo(arr, N);
        Console.Write(ans);
    }
}
 
// This code is contributed by devendra solunke

// javascript program to check missingNo
<script>
        var arr = [ 1, 2, 3, 5 ];
        var N = arr.length;
        var ans = getMissingNo(arr, N);
        console.log(ans);
 
   // Function to find the missing number
   function getMissingNo(arr, n)
    {
        var i = 0;
        while (i < n) {
            // as array is of 1 based indexing so the
            // correct position or index number of each
            // element is element-1 i.e. 1 will be at 0th
            // index similarly 2 correct index will 1 so
            // on...
            var correctpos = arr[i] - 1;
            if (arr[i] < n && arr[i] != arr[correctpos]) {
                // if array element should be lesser than
                // size and array element should not be at
                // its correct position then only swap with
                // its correct positioin or index value
                swap(arr, i, correctpos);
            }
            else {
                // if element is at its correct position
                // just increment i and check for remaining
                // array elements
                i++;
            }
        }
      // check for missing element by comparing elements with their index values
        for (var index = 0; index < arr.length; index++) {
            if (arr[index] != index + 1) {
                return index + 1;
            }
        }
        return n;
    }
 
    function swap(arr, i, correctpos)
    {
      // swap elements with their correct indexes
        var temp = arr[i];
        arr[i] = arr[correctpos];
        arr[correctpos] = temp;
    }
</script>
// this code is contributed by devendra solunke

4

Complejidad temporal: O(N), requiere comparaciones (N-1)
Complejidad auxiliar: O(1)