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[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.

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[8] = {1, 4, 6, 2, 5, 8, 7, 9};
 
    printf("Missing Number : %d \n", getMissingNumber(array, 8));

    return 0;
}

Output

Missing Number : 3