# C Program to Find Missing Number in Array

• 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.
Time Complexity : O(n)
```#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 = {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.
Time Complexity : O(n)

## 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 = {1, 4, 6, 2, 5, 8, 7, 9};

printf("Missing Number : %d \n", getMissingNumber(array, 8));

return 0;
}
```
Output
```Missing Number : 3
```