CODEWITHSUNDEEP
c++algorithmdata-structuresc++17
BeruboIV
BeruboIV

Reputation: 151

Please explain this process for finding the missing number in 1...N

We are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. We have to find the missing number. This is the question.

My approach is to take XOR of all the elements from 1...N and all the elements of the array and then output the XOR. It works fine, but I found one more solution in Geeks for Geeks but I am not able to understand what and why the are doing it.

Approach: We can pick one number from known numbers and subtract one number from given numbers

Code:

#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; 
}

Upvotes: 0

Views: 903

Answers (3)

backdoor
backdoor

Reputation: 901

int i, total=1;

As we have declared total as an integer, there may be overflow while adding all the number if addition exceeds the integer upper bound.

so, to overcome this problem we are adding (from 1 to N) and subtracting (Elements of the array a[]) from total simultaneously.

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

Upvotes: 3

Mayank Raj
Mayank Raj

Reputation: 1

Inside the for loop:

Summation will add-up from '1' to 'N'.
While, subtraction will add-up all the array elements with negative sign.

So, finally total variable will store only the missing number:

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

Upvotes: 0

MaximumBoy
MaximumBoy

Reputation: 71

Use the sum formula:

sum from i = 1 to N = N * (N + 1) / 2

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

Add the numbers in the list. Subtract this from the sum of the numbers and you have your missing number.

Upvotes: 3

Related Questions