Encuentre el número que falta en una array ordenada de rango limitado

Dada una array ordenada de tamaño n y dado que hay números del 1 al n+1 con uno faltante, se debe encontrar el número faltante. Se puede suponer que la array tiene elementos distintos.

Ejemplos: 

Entrada: 1 3 4 5 6
Salida: 2

Entrada: 1 2 3 4 5 7 8 9 10
Salida: 6

Atravesamos todos los elementos. Para cada elemento a[i], comprobamos si es igual a i+1 o no. Si no, devolvemos (i+1). 

Implementación:

// C++ program to find missing Number in
// a sorted array of size n and distinct
// elements.
#include<bits/stdc++.h>
using namespace std;
 
// Function to find missing number
int getMissingNo(int a[], int n)
{
    for (int i=0; i<n; i++)       
        if (a[i] != (i+1))
            return (i+1);
  
    // If all numbers from 1 to n
    // are present
    return n+1;
}
 
// Driver code
int main()
{
    int a[] = {1, 2, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    cout << getMissingNo(a, n);
    return 0;
}
 
// This code is contributed by Sachin Bisht

// Java program to find missing Number in
// a sorted array of size n and distinct
// elements.
class Main
{
    // Function to find missing number
    static int getMissingNo(int a[])
    {
        int n = a.length;
        for (int i=0; i<n; i++)       
            if (a[i] != (i+1))
                return (i+1);
 
        // If all numbers from 1 to n
        // are present
        return n+1;
    }
       
    /* program to test above function */
    public static void main(String args[])
    {
        int a[] = {1, 2, 4, 5, 6};
        System.out.println(getMissingNo(a));
    }
}

# Python program to find missing Number in
# a sorted array of size n and distinct
# elements.
 
# function to find missing number
def getMissingNo(a):
    n = len(a)
     
    for i in range(n):
        if(a[i] != i + 1):
            return i + 1
             
    # If all numbers from 1 to n
    # are present
    return n+1
 
# Driver code
a = [1, 2, 4, 5, 6]
print(getMissingNo(a))
 
# This code is contributed by Sachin Bisht

// C# program to find missing Number
// in a sorted array of size n and
// distinct elements.
using System;
 
class GFG
{
     
// Function to find missing number
static int getMissingNo(int []a, int n)
{
    for (int i = 0; i < n; i++)
        if (a[i] != (i + 1))
            return (i + 1);
 
    // If all numbers from
    // 1 to n are present
    return n + 1;
}
 
// Driver code
public static void Main()
{
    int []a = {1, 2, 4, 5, 6};
    int n = a.Length;
    Console.WriteLine(getMissingNo(a, n));
}
}
 
// This code is contributed by ihritik

<?php
// PHP program to find missing Number
// in a sorted array of size n and
// distinct elements.
 
// Function to find missing number
function getMissingNo($a, $n)
{
    for ($i = 0; $i < $n; $i++)
        if ($a[$i] != ($i + 1))
            return ($i + 1);
 
    // If all numbers from
    // 1 to n are present
    return $n + 1;
}
 
// Driver code
$a = array(1, 2, 4, 5, 6);
$n = sizeof($a);
echo getMissingNo($a, $n);
 
// This code is contributed
// by ihritik
?>

<script>
// javascript program to find missing Number
// in a sorted array of size n and
// distinct elements.
     
// Function to find missing number
function getMissingNo(a,n)
{
    for (let i = 0; i < n; i++)
        if (a[i] != (i + 1))
            return (i + 1);
 
    // If all numbers from
    // 1 to n are present
    return n + 1;
}
 
// Driver code
let a = [1, 2, 4, 5, 6]
let n = a.length;
document.write(getMissingNo(a, n));
 
// This code is contributed by mohit kumar 29.
</script>

3

Complejidad de tiempo: O(N) , donde N es la longitud de la array dada.
Espacio Auxiliar: O(1)

Otro enfoque: (Use un enfoque matemático para resolver este problema)

Se da, los elementos en la array están en el rango de [1, n + 1] , así que primero calcule la suma total requerida sumando todos los números de 1 a n + 1, esto se puede calcular usando la fórmula de » suma de los primeros N números naturales” por suma = N*(N+1) / 2 , donde N son los primeros N números naturales. Después de eso, reste la suma total requerida por la suma actual de la array dada. Esto dará como resultado el número faltante que no está presente en la array dada.

Implementación:

// C++ program to find missing Number in
// a sorted array of size n and distinct
// elements.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find missing number
int getMissingNo(int a[], int n)
{
    // Total sum required
    int total_sum = ((n + 1) * (n + 2)) / 2;
 
    // Current sum of given array
    int sum = 0;
 
    for (int i = 0; i < n; i++)
        sum += a[i];
 
    return total_sum - sum;
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 4, 5, 6 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << getMissingNo(a, n);
    return 0;
}
 
// This code is contributed by Pushpesh Raj

3

Complejidad de tiempo: O(N) , donde N es la longitud de la array dada.
Espacio Auxiliar: O(1)

Este artículo es una contribución de Balaguru . 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.