Description: We are given a list of ‘n-1’ numbers, all lying between 1 to n. We have to find the number that lies between 1 and n, but isn’t present in the list.
If video does not load, Click here
1 2 3 5 6
Method 1:Using summation of natural nos
1.Calculate sum of all elements in the list and store value in ‘x’.
2.Sum of first ‘n’ natural nos is given by:
3.Missing number: y - x
Time Complexity: O(n)
Method 2:Using xor
1. Intialize x=0 and y=0.
2. Perform bitwise xor of all number from 1 to n using variable ‘x’.
3. Perform bitwise xor of all numbers present in the list using variable ‘y’.
4. Missing no: x (xor) y
/*The following function returns missing number using Method 1.*/