Find Missing Number in Array Using XOR and Gauss Sum in C

Finding a missing number from a sequence is a common problem in programming and technical interviews.

Given an array containing numbers from 0 to n with one number missing, we can solve this efficiently using XOR or mathematical formulas.

In this tutorial, we will explore both approaches in C.

Concept Overview

We are given n distinct numbers in the range 0 to n.

One number is missing, and our task is to find it.

Efficient solutions avoid sorting or extra memory.

Problem Statement

Given an array of size n containing numbers from 0 to n with one missing, find the missing number.

Example

Input:
Array: 0 1 3 4 5

Output:
Missing Number: 2

Approach 1: XOR Method

XOR of a number with itself is 0, and XOR with 0 gives the number.

So if we XOR all array elements and all numbers from 0 to n, the result will be the missing number.

#include <stdio.h>

int findMissingXOR(int arr[], int n) {
    int xor1 = 0, xor2 = 0;

    for (int i = 0; i < n; i++) {
        xor1 ^= arr[i];
    }

    for (int i = 0; i <= n; i++) {
        xor2 ^= i;
    }

    return xor1 ^ xor2;
}

int main() {
    int arr[] = {0, 1, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Missing Number (XOR): %d", findMissingXOR(arr, n));

    return 0;
}

Approach 2: Gauss Sum Formula

The sum of numbers from 0 to n is given by the formula:

Sum = n * (n + 1) / 2

Subtract the sum of array elements from this value to get the missing number.

#include <stdio.h>

int findMissingSum(int arr[], int n) {
    int total = n * (n + 1) / 2;
    int sum = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }

    return total - sum;
}

int main() {
    int arr[] = {0, 1, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Missing Number (Sum): %d", findMissingSum(arr, n));

    return 0;
}

Output

Missing Number (XOR): 2
Missing Number (Sum): 2

Detailed Explanation

In the XOR method, all numbers cancel out except the missing one.

In the sum method, we calculate expected sum and subtract actual sum.

Both methods run in linear time.

Time and Space Complexity

Time Complexity: O(n)

Space Complexity: O(1)

Comparison of Methods

XOR method avoids overflow issues.

Sum method is simpler but may overflow for large n.

Applications

Used in data validation and error detection.

Common in competitive programming and interviews.

Advantages

Efficient and easy to implement.

No extra memory required.

Limitations

Assumes exactly one missing number.

Works only for range 0 to n.

Improvements You Can Make

Extend solution to find multiple missing numbers.

Handle unsorted or duplicate elements.

Use bit manipulation techniques for advanced problems.

Mastering XOR-based problems will greatly improve your algorithmic thinking.