C Program to Find Missing Number in Array

You can find the missing number in an array of size n-1 containing numbers from 1 to n by calculating the expected sum with n*(n+1)/2 and subtracting the actual sum of array elements; the difference is the missing number.

Examples

InputArray: [1, 2, 4, 5, 6], n = 6

Output3

InputArray: [2, 3, 1, 5], n = 5

Output4

InputArray: [1], n = 2

Output2

How to Think About It

To find the missing number, first understand that the array should have all numbers from 1 to n, but one is missing. Calculate the total sum of numbers from 1 to n using the formula n*(n+1)/2. Then add all numbers in the array. The missing number is the difference between the total sum and the sum of array elements.

Algorithm

1

Get the size n of the full range (1 to n).

2

Calculate the expected sum using the formula n*(n+1)/2.

3

Calculate the sum of all elements in the given array.

4

Subtract the array sum from the expected sum to find the missing number.

5

Return or print the missing number.

Code

c

#include <stdio.h>

int findMissingNumber(int arr[], int size, int n) {
    int total = n * (n + 1) / 2;
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return total - sum;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int n = 6;
    int size = sizeof(arr) / sizeof(arr[0]);
    int missing = findMissingNumber(arr, size, n);
    printf("Missing number is %d\n", missing);
    return 0;
}

Dry Run

Let's trace the example array [1, 2, 4, 5, 6] with n=6 through the code.

1

Calculate total sum

total = 6 * (6 + 1) / 2 = 21

2

Sum array elements

sum = 1 + 2 + 4 + 5 + 6 = 18

3

Find missing number

missing = total - sum = 21 - 18 = 3

Iteration	Array Element	Running Sum
1	1	1
2	2	3
3	4	7
4	5	12
5	6	18

Why This Works

Step 1: Calculate expected sum

Using the formula n*(n+1)/2 gives the sum of all numbers from 1 to n if none were missing.

Step 2: Sum actual array elements

Add all numbers present in the array to find the current total.

Step 3: Subtract to find missing

The difference between expected sum and actual sum is the missing number.

Alternative Approaches

Using XOR operation

c

#include <stdio.h>

int findMissingXOR(int arr[], int size, int n) {
    int xor_all = 0, xor_arr = 0;
    for (int i = 1; i <= n; i++) {
        xor_all ^= i;
    }
    for (int i = 0; i < size; i++) {
        xor_arr ^= arr[i];
    }
    return xor_all ^ xor_arr;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int n = 6;
    int size = sizeof(arr) / sizeof(arr[0]);
    int missing = findMissingXOR(arr, size, n);
    printf("Missing number is %d\n", missing);
    return 0;
}

This method uses XOR to cancel out all numbers present, leaving the missing number; it avoids overflow but is slightly more complex.

Using boolean visited array

c

#include <stdio.h>
#include <stdbool.h>

int findMissingVisited(int arr[], int size, int n) {
    bool visited[n+1];
    for (int i = 0; i <= n; i++) visited[i] = false;
    for (int i = 0; i < size; i++) {
        visited[arr[i]] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) return i;
    }
    return -1; // no missing
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int n = 6;
    int size = sizeof(arr) / sizeof(arr[0]);
    int missing = findMissingVisited(arr, size, n);
    printf("Missing number is %d\n", missing);
    return 0;
}

This method uses extra space to track visited numbers; it is simple but uses O(n) space.

Complexity: O(n) time, O(1) space

Time Complexity

The program loops once through the array to sum elements, so it runs in O(n) time where n is the number of elements.

Space Complexity

Only a few variables are used for sums and counters, so space complexity is O(1), constant space.

Which Approach is Fastest?

The sum formula method is fastest and simplest; XOR is also O(n) but avoids overflow; the visited array uses extra space and is slower.

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simple and fast for small to medium n
XOR operation	O(n)	O(1)	Avoids overflow, good for large n
Visited array	O(n)	O(n)	Easy to understand, uses extra memory