Styjun

Given an array C of size N-1 and given that there are numbers from 1 to N with one element missing, the missing number is to be found.

Input:

The first line of input contains an integer T denoting the number of test cases. For each test case first line contains N(size of array). The subsequent line contains N-1 array elements.

Output:

Print the missing number in array.

Constraints:

1 ≤ T ≤ 200

1 ≤ N ≤ 107

1 ≤ C[i] ≤ 107

Example:

Input:

2
5
1 2 3 5
10
1 2 3 4 5 6 7 8 10

Output:

4
9

i have done this in c++

#include <iostream>
using namespace std;

int main() 
int a,n,arr[50],j=1,element;
int sum,total[50],i;
cin>>n;
a=n;
while(n!=0)

 cin>>element;
 sum=0;
 total[j]=0;
 for(i=1;i<=element-1;i++)
 
 cin>>arr[i];
 sum=sum+arr[i];
 
 total[j]=(element*(element+1)/2) -sum;
 j++;
 n--;

for(i=1;i<=a;i++)

 cout<<total[i]<<endl;

return 0;

Output:

4
9

Try this as a test case:

2
55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
55
33 54 1 55 23 51 35 5 49 26 43 42 41 32 7 14 9 50 34 29 37 25 52 24 8 53 15 45 44 19 39 47 17 48 38 21 36 31 3 18 46 20 6 27 12 11 16 10 2 13 28 4 30 22

your code should then crash under your control, and then you can find out why.

Think hard about the constraints you were given for various values and how your code operates at the edges of those constraints.

Also, there is a way to solve this problem that doesn't require you to use any arrays at all. It's the fastest way to solve the problem.

Because you have declared the array of size 50 blocks.

But , according to given constraints : 1 ≤ N ≤ 107 , 1 ≤ C[i] ≤ 107

if you take value of element more than 50 , it will give segmentation fault because the maximum size of array is 50.

So , increase the size of arrays to arr[107]; and total[107];

And then submit the solution , it would work then.

One of the best solution for finding Missing element is using XOR operator :

Question: You 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 integer is missing in the list.
Now, we need to find that missing number.

Solution :

Method 1 : By finding sum of first “n” natural numbers.

Step 1 : First, find the sum of all numbers from 1 to n ( means find the sum of first “n” natural numbers)

Step 2 : Subtract each element (all elements) of the given list from the sum. And we’ll get the missing number.

Note : There might be an integer overflow while adding large numbers in method 1 solution.

Method 2: Using XOR operator :

Remember these properties : n ^ n = 0 AND n ^ 0 = n

Step 1: We’ll take the xor of all numbers from 1 to n (Means, we’ll take xor of first “n” natural numbers).

Step 2: We’ll take the xor of all elements of the given array (list).

Step 3: xor of Step 1 and Step 2 will give the required missing number.

Example : Given list arr = [4,2,1,6,8,5,3,9] n=9 (given)

Step1 : Step1_result = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1

Step2 : Step2_result = 4 ^ 2 ^ 1 ^ 6 ^ 8 ^ 5 ^ 3 ^ 9 = 6

Step3 : Final_Result = Step1_result ^ Step2_result = 1 ^ 6 = 7

But, How Final_Result calculated the missing number ?

Final_Result= ( 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ) ^ ( 4 ^ 2 ^ 1 ^ 6 ^ 8 ^ 5 ^ 3 ^ 9 ) 

So , here ,

Final_Result = (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ) ^ ( 4 ^ 2 ^ 1 ^ 6 ^ 8 ^ 5 ^ 3 ^ 9 )

= 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 4 ^ 2 ^ 1 ^ 6 ^ 8 ^ 5 ^ 3 ^ 9

= ( 1 ^ 1 ) ^ ( 2 ^ 2 ) ^ ( 3 ^ 3 ) ^ ( 4 ^ 4 ) ^ ( 5 ^ 5 ) ^ ( 6 ^ 6 ) ^ (7) ^ ( 8 ^ 8 ) ^ ( 9 ^ 9 )

= 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 7 ^ 0 ^ 0 ( property applied )

= 0 ^ 7 ( because we know 0 ^ 0 = 0 )

= 000 ^ 111

= 111

= 7 ( Required Result )