- Write a program in C to find missing number using XOR bitwise operator in linear time.

Given an integer array of size N having number from 1 to N+1. There are no duplicate elements in input array all array elements are unique. One number between 1 to N+1 is missing , we have to print that missing number using only constant amount of memory space.

For Example :

Input Array : 4 2 6 5 1

Missing Number is 3

Let inputArray be an integer array of size N.

**By finding sum of all array element**

- Traverse the inputArray and find the sum of all elements from index 0 to N-1. Let the sum of all array elements be ARRAY_SUM.
- Find the sum of all number between 1 to N+1 as ((N+1)*(N+2))/2. Let this sum be TOTAL_SUM.
- Missing number = TOTAL_SUM - ARRAY_SUM.

#include <stdio.h> int getMissingNumber(int *array, int size) { int i, sum = 0, n = size + 1; /* Take the sum of all array elements */ for(i = 0; i < size; i++){ sum = sum + array[i]; } return (n*(n+1))/2 - sum; } int main(){ int array[8] = {1, 4, 6, 2, 5, 8, 7, 9}; printf("Missing Number : %d \n", getMissingNumber(array, 8)); return 0; }Output

Missing Number : 3

**Using XOR bitwise operator**

- Traverse the inputArray and find the XOR of all array elements. Let the result of this XOR be of all array elements be ARRAY_XOR.
- Find the XOR of all number between 1 to N+1. Let the result of this XOR be TOTAL_XOR.
- The main logic behind this algorithm is that "XOR of a number with itself is 0"(A^A = 0). When we do XOR of TOTAL_XOR and ARRAY_XOR then all array elements XOR becomes zero leaving only the missing number.
- Missing number = XOR of TOTAL_XOR and ARRAY_XOR.

## C program to find missing number using XOR bitwise operator

#include <stdio.h> int getMissingNumber(int *array, int size) { int i, xorResult = 0, n = size + 1; /* Take the xor of all numbers between 1 to n */ for(i = 1; i <= n; i++){ xorResult = xorResult ^ i; } /* Take the xor of all array elements */ for(i = 0; i < size; i++){ xorResult = xorResult ^ array[i]; } return xorResult; } int main(){ int array[8] = {1, 4, 6, 2, 5, 8, 7, 9}; printf("Missing Number : %d \n", getMissingNumber(array, 8)); return 0; }Output

Missing Number : 3