Пожалуйста, объясните этот процесс для поиска пропущенного числа в 1 ... N

Question

Нам дан список из n-1 целых чисел, и эти числа находятся в диапазоне от 1 до n. В списке нет дубликатов. Одно из целых чисел отсутствует в списке. Мы должны найти пропущенный номер. Это вопрос.

Мой подход состоит в том, чтобы взять XOR всех элементов из 1 ... N и всех элементов массива и затем вывести XOR. Это работает нормально, но я нашел еще одно решение в Geeks для Geeks, но я не могу понять, что и почему они делают.

Подход : Мы можем выбрать одно число из известных числа и вычесть одно число из заданных чисел

код :

#include <bits/stdc++.h> 
using namespace std; 

// a represents the array 
// n : Number of elements in array a 
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}; 
    cout<<getMissingNo(arr,sizeof(arr)/sizeof(arr[0])); 
    return 0; 
}

Answer 1

int i, total=1; 

Поскольку мы объявили итоговое значение как целое число, при добавлении всего числа может возникнуть переполнение, если сложение превышает верхнюю границу целого числа.

, поэтому для преодоления этой проблемы, которую мы добавляем (из 1 к N) и вычитая (элементы массива a []) из общего количества одновременно.

for ( i = 2; i<= (n+1); i++) 
{ 
    total+=i; 
    total -= a[i-2]; // This will reduce the total so that overflow does not happen.
} 

Answer 2

Используйте формулу суммы:

сумма от i = 1 до N = N * (N + 1) / 2

https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

Добавьте цифры в список. Вычтите это из суммы чисел, и у вас будет пропущенное число.

Answer 3

Внутри для l oop:

Summation will add-up from '1' to 'N'.

While, subtraction will add-up all the array elements with negative sign.

Итак, в итоге в переменной total будет храниться только пропущенное число:

As total= sum(1 to N) - sum(array elements)= missing number.