Encuentra el número que falta en el rango

Dada una array de tamaño n. También se da que el rango de números es desde el número más pequeño hasta el número más pequeño + n donde el número más pequeño es el número más pequeño en la array. La array contiene un número en este rango, pero falta un número, por lo que la tarea es encontrar este número faltante.
Ejemplos: 
 

Input  :  arr[] = {13, 12, 11, 15}
Output :  14

Input  :  arr[] = {33, 36, 35, 34};
Output : 37

El problema está muy cerca de encontrar el número que falta .
Hay muchos enfoques para resolver este problema. 
Un enfoque simple es primero encontrar el mínimo, luego uno por uno buscar todos los elementos. La complejidad temporal de este enfoque es O(n*n)
Una mejor solución es ordenar la array. Luego recorra la array y encuentre el primer elemento que no está presente. La complejidad temporal de este enfoque es O(n Log n)
La mejor solución es primero XOR todos los números. Luego XOR este resultado a todos los números desde el número más pequeño hasta n+número más pequeño. El XOR es nuestro resultado.
Ejemplo:- 
 

arr[n] = {13, 12, 11, 15}
smallestNumber = 11

first find the xor of this array
13^12^11^15 = 5

Then find the XOR first number to first number + n
11^12^13^14^15 = 11;

Then xor these two number's
5^11 = 14 // this is the missing number

// CPP program to find missing
// number in a range.
#include <bits/stdc++.h>
using namespace std;
 
// Find the missing number
// in a range
int missingNum(int arr[], int n)
{
    int minvalue = *min_element(arr, arr+n);
 
    // here we xor of all the number
    int xornum = 0;
    for (int i = 0; i < n; i++) {
        xornum ^= (minvalue) ^ arr[i];
        minvalue++;
    }
 
    // xor last number
    return xornum ^ minvalue;
}
 
// Driver code
int main()
{
    int arr[] = { 13, 12, 11, 15 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << missingNum(arr, n);
    return 0;
}

// Java program to find
// missing number in a range.
import java.io.*;
import java.util.*;
 
class GFG {
     
// Find the missing number in a range
static int missingNum(int arr[], int n)
{
    List<Integer> list = new ArrayList<>(arr.length);
    for (int i :arr)
    {
        list.add(Integer.valueOf(i));
    }
    int minvalue = Collections.min(list);;
  
    // here we xor of all the number
    int xornum = 0;
    for (int i = 0; i < n; i++) {
        xornum ^= (minvalue) ^ arr[i];
        minvalue++;
    }
  
    // xor last number
    return xornum ^ minvalue;
}
 
public static void main (String[] args) {
     int arr[] = { 13, 12, 11, 15 };
    int n = arr.length;
    System.out.println(missingNum(arr, n));  
 
    }
}
 
//This code is contributed by Gitanjali.

# python3 program to check
# missingnumber in a range
 
# Find the missing number
# in a range
def missingNum( arr,  n):
 
    minvalue = min(arr)
  
    # here we xor of all the number
    xornum = 0
    for  i in range (0,n):
        xornum ^= (minvalue) ^ arr[i]
        minvalue = minvalue+1
     
  
    # xor last number
    return xornum ^ minvalue
     
# Driver method
arr = [ 13, 12, 11, 15 ]
n = len(arr)
print (missingNum(arr, n))
 
# This code is contributed by Gitanjali.

// C# program to find
// missing number in a range.
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
     
// Find the missing number in a range
static int missingNum(int []arr, int n)
{
    List<int> list = new List<int>(arr.Length);
    foreach (int i in arr)
    {
        list.Add(i);
    }
    int minvalue = list.Min();
 
    // here we xor of all the number
    int xornum = 0;
    for (int i = 0; i < n; i++)
    {
        xornum ^= (minvalue) ^ arr[i];
        minvalue++;
    }
 
    // xor last number
    return xornum ^ minvalue;
}
 
// Driver Code
public static void Main (String[] args)
{
    int []arr = { 13, 12, 11, 15 };
    int n = arr.Length;
    Console.WriteLine(missingNum(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

<?php
// PHP program to find missing
// number in a range.
 
// Find the missing number
// in a range
function missingNum($arr, $n)
{
    $minvalue = min($arr);
 
    // here we xor of all the number
    $xornum = 0;
    for ($i = 0; $i < $n; $i++)
    {
        $xornum ^= ($minvalue) ^ $arr[$i];
        $minvalue++;
    }
 
    // xor last number
    return $xornum ^ $minvalue;
}
 
// Driver code
$arr = array( 13, 12, 11, 15 );
$n = sizeof($arr);
echo missingNum($arr, $n);
     
// This code is contributed
// by Sach_Code
?>

<script>
// Javascript program to find missing
// number in a range.
 
// Find the missing number
// in a range
function missingNum(arr, n)
{
    let minvalue = Math.min(...arr);
 
    // here we xor of all the number
    let xornum = 0;
    for (let i = 0; i < n; i++) {
        xornum ^= (minvalue) ^ arr[i];
        minvalue++;
    }
 
    // xor last number
    return xornum ^ minvalue;
}
 
// Driver code
    let arr = [ 13, 12, 11, 15 ];
    let n = arr.length;
    document.write(missingNum(arr, n));
 
</script>

14

Otro enfoque:

Se puede realizar un enfoque eficiente para encontrar el número que falta utilizando el concepto de que la suma de la progresión aritmética número más pequeño, número más pequeño + 1, número más pequeño + 2, ….., número más pequeño + n, que es (n + 1) x (2 número más pequeño + 1)/2 es igual a la suma de la array + el número que falta.

En otras palabras,

Suma del AP – Suma de la array = Número faltante.

La ventaja de este método es que podemos utilizar los métodos de biblioteca incorporados para calcular la suma y el número mínimo de la array, lo que reducirá el tiempo de ejecución, especialmente para lenguajes como Python3 y JavaScript.

// CPP program to find missing
// number in a range.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the missing number
// in a range
int missingNum(int arr[], int n)
{
    // calculating the minimum of the array
    int& minNum = *min_element(arr, arr + n);
    // calculating the sum of the array
    int arrSum = 0;
    arrSum = accumulate(arr, arr + n, arrSum);
    // calculating the sum of the range [min, min + n]
    // given using the AP series sum formula
    // (n + 1) * (2 * min + 1) / 2
    int rangeSum = (minNum + minNum + n) * (n + 1) / 2;
    // the difference between the sum of range
    // and the sum of array is the missing element
    return rangeSum - arrSum;
}
 
// Driver code
int main()
{
    int arr[] = { 13, 12, 11, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // function call
    cout << missingNum(arr, n);
    return 0;
}
 
// this code is contributed by phasing17

// Java program to find missing
// number in a range.
 
import java.util.stream.*;
 
class GFG {
 
    // Function to find the missing number
    // in a range
    static int missingNum(int[] arr, int n)
    {
        // calculating the minimum of the array
        int minNum = IntStream.of(arr).min().getAsInt();
        // calculating the sum of the array
        int arrSum = IntStream.of(arr).sum();
 
        // calculating the sum of the range [min, min + n]
        // given using the AP series sum formula
        // (n + 1) * (2 * min + 1) / 2
        int rangeSum = (minNum + minNum + n) * (n + 1) / 2;
        // the difference between the sum of range
        // and the sum of array is the missing element
        return rangeSum - arrSum;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 13, 12, 11, 15 };
        int n = arr.length;
        // function call
        System.out.println(missingNum(arr, n));
    }
}
 
//this code is contributed by phasing17

# Python3 program to find missing
# number in a range.
 
 
# Function to find the missing number
# in a range
def missingNum(arr, n):
    # calculating the minimum of the array
    minNum = min(arr)
    #  calculating the sum of the array
    arrSum = sum(arr)
 
    # calculating the sum of the range [min, min + n]
    # given using the AP series sum formula
    # (n + 1) * (2 * min + 1) / 2
    rangeSum = (minNum + minNum + n) * (n + 1) // 2
    # the difference between the sum of range
    # and the sum of array is the missing element
    return rangeSum - arrSum
 
 
# Driver code
arr = [13, 12, 11, 15]
n = len(arr)
# function call
print(missingNum(arr, n))
 
 
# this code is contributed by phasing17

// C# program to find missing
// number in a range.
using System;
using System.Linq;
 
class GFG {
 
  // Function to find the missing number
  // in a range
  static int missingNum(int[] arr, int n)
  {
    // calculating the minimum of the array
    int minNum = arr.Min();
 
    // calculating the sum of the array
    int arrSum = arr.Sum();
 
    // calculating the sum of the range [min, min + n]
    // given using the AP series sum formula
    // (n + 1) * (2 * min + 1) / 2
    int rangeSum = (minNum + minNum + n) * (n + 1) / 2;
 
    // the difference between the sum of range
    // and the sum of array is the missing element
    return rangeSum - arrSum;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int[] arr = { 13, 12, 11, 15 };
    int n = arr.Length;
 
    // function call
    Console.WriteLine(missingNum(arr, n));
  }
}
 
// this code is contributed by phasing17

//JS program to find missing
// number in a range.
 
 
// Function to find the missing number
// in a range
function missingNum(arr, n)
{
    // calculating the minimum of the array
    var minNum = Math.min(...arr);
    //  calculating the sum of the array
    var arrSum = arr.reduce((a, b) => a + b, 0);
     
    // calculating the sum of the range [min, min + n]
    // given using the AP series sum formula
    // (n + 1) * (2 * min + 1) / 2
    var rangeSum = Number((minNum + minNum + n) * (n + 1) / 2);
    // the difference between the sum of range
    // and the sum of array is the missing element
    return rangeSum - arrSum;
}
 
// Driver code
var arr = [ 13, 12, 11, 15 ];
var n = arr.length;
// function call
console.log(missingNum(arr, n));
 
 
// this code is contributed by phasing17

14

Complejidad de tiempo: O(n)

Espacio Auxiliar : O(1)