C Program to find multiple missing numbers from a sequence

When a sequence should contain every integer from 1 through n, more than one value may be absent from the supplied array. A presence array can record which values occur and then reveal every missing number in one scan.

For example:

Complete sequence: 1 2 3 4 5 6 7 8 9 10
Given array:       2 3 5 6 8 9 10
Missing numbers:   1 4 7

The supplied values may appear in any order. The program does not need to sort them.

Assumptions

This program uses the following definition of the problem:

• The complete sequence contains every integer from 1 to n.
• The input array contains zero or more distinct values from that range.
• Any number of values may be missing.
• The input order is arbitrary.

The code validates the value range and rejects duplicate input so that these assumptions remain clear.

C Program to Find All Missing Numbers from 1 to n

#include <stdio.h>

#define MAX_N 100

int main(void) {
    int sequence[MAX_N];
    int present[MAX_N + 1] = {0};
    int n;
    int size;
    int missingCount = 0;

    printf("Enter the upper limit n: ");
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) {
        printf("Please enter n between 1 and %d.\n", MAX_N);
        return 1;
    }

    printf("Enter the number of supplied elements: ");
    if (scanf("%d", &size) != 1 || size < 0 || size > n) {
        printf("Please enter a size between 0 and %d.\n", n);
        return 1;
    }

    printf("Enter %d distinct elements from 1 to %d:\n", size, n);
    for (int index = 0; index < size; index++) {
        if (scanf("%d", &sequence[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }

        if (sequence[index] < 1 || sequence[index] > n) {
            printf("Every element must be between 1 and %d.\n", n);
            return 1;
        }

        if (present[sequence[index]]) {
            printf("Duplicate element %d is not allowed.\n",
                   sequence[index]);
            return 1;
        }

        present[sequence[index]] = 1;
    }

    printf("Missing numbers: ");
    for (int number = 1; number <= n; number++) {
        if (!present[number]) {
            printf("%d ", number);
            missingCount++;
        }
    }

    if (missingCount == 0) {
        printf("None");
    }

    printf("\nTotal missing numbers: %d\n", missingCount);

    return 0;
}

Sample Output

Enter the upper limit n: 10
Enter the number of supplied elements: 7
Enter 7 distinct elements from 1 to 10:
2 3 5 6 8 9 10
Missing numbers: 1 4 7
Total missing numbers: 3

How the Presence Array Works

The present array uses each possible sequence value as an index:

int present[MAX_N + 1] = {0};

All positions initially contain 0, meaning “not seen.” Whenever a value is read, its matching position is set to 1:

present[sequence[index]] = 1;

If the input contains 5, then present[5] becomes 1. After all input values have been processed, any index from 1 through n that still contains 0 represents a missing number.

Index 0 is intentionally unused because the expected sequence begins at 1. The array needs MAX_N + 1 positions so that index MAX_N is valid.

Dry Run

For n = 10 and the array 2 3 5 6 8 9 10, the presence information is:

Number	1	2	3	4	5	6	7	8	9	10
Present?	No	Yes	Yes	No	Yes	Yes	No	Yes	Yes	Yes

Scanning the table from index 1 to index 10 finds zeros at indices 1, 4, and 7. Those indices are printed as the missing numbers.

Why Is a Presence Array Useful for Multiple Missing Values?

Every possible number has its own marker, so the algorithm retains separate information about each value. This is important because a single total or combined value cannot generally identify several missing numbers.

For example, a sum difference of 10 might mean that 3 and 7 are missing, but it could also represent 4 and 6. A presence array distinguishes these cases directly.

Why Does the Program Ask for Two Sizes?

The variables have different meanings:

• n is the largest value in the complete sequence 1 through n.
• size is the number of values that were actually supplied.

If the values are distinct and valid, the number missing is also n - size. However, the presence scan is still needed to determine which values are absent.

Why Validate Duplicates?

A duplicate value does not mark a new sequence number as present. For example:

n = 6
Input: 1 2 2 5

The repeated 2 does not provide information about another value. Rejecting it prevents the stated array size from being mistaken for the number of distinct supplied values.

The program detects a duplicate before marking the value again:

if (present[sequence[index]]) {
    printf("Duplicate element %d is not allowed.\n",
           sequence[index]);
    return 1;
}

Why Validate the Range?

The input value becomes an array index. A value below 1 or above n does not belong to the expected sequence and could also access an invalid position if it exceeded MAX_N.

Range validation therefore protects both the meaning of the result and memory safety.

What If No Number Is Missing?

When the input contains every number from 1 through n, each presence marker is 1. The program prints None and reports a count of zero:

n = 5
Input: 1 2 3 4 5
Missing numbers: None
Total missing numbers: 0

What If Every Number Is Missing?

The program accepts size = 0. No input elements are read, every presence marker remains zero, and the complete sequence is printed as missing:

n = 5
Supplied elements: 0
Missing numbers: 1 2 3 4 5
Total missing numbers: 5

What If the Input Is Unsorted?

Input order has no effect because every value sets its own presence marker:

n = 8
Input: 8 2 6 1 4
Missing numbers: 3 5 7

The missing values are printed in ascending order because the final loop scans indices from 1 through n.

Why the Single-Number Sum Method Is Not Enough

For one missing value, subtracting the actual sum from the expected sum identifies that value. With multiple missing values, the subtraction produces only their combined sum.

Likewise, a single XOR result does not generally identify several absent values without additional conditions. The presence-array method works for any number of missing values under the stated range limit.

Alternative Approach Using Nested Loops

Without a presence array, the program could search the input array for every candidate from 1 to n:

for (int number = 1; number <= n; number++) {
    int found = 0;

    for (int index = 0; index < size; index++) {
        if (sequence[index] == number) {
            found = 1;
            break;
        }
    }

    if (!found) {
        printf("%d ", number);
    }
}

This requires only constant auxiliary space, but its worst-case running time is O(n × size). The presence array exchanges additional memory for faster lookup.

Other Approaches

• Sort and scan: Sort the supplied values, then detect gaps between consecutive numbers. This usually takes O(size log size) time and may modify the input.
• Boolean or bit set: A boolean array follows the same idea with smaller logical elements. A bit set can reduce memory further for very large ranges.
• Hash set: Useful when the value range is large or sparse, but standard C does not include a built-in hash-set type.
• Cyclic placement: Values in a tightly bounded range can be moved toward their matching indices, though duplicate and validation rules require care.

What If the Sequence Does Not Start at 1?

For a consecutive range from first to last, map each value to a zero-based presence index:

index = value - first

The presence array then needs last - first + 1 positions. When an unmarked index i is found, the corresponding missing value is first + i.

Time and Space Complexity

Let n be the size of the complete sequence and m be the number of supplied values.

• Time complexity: O(n + m). Marking takes O(m), and scanning the possible values takes O(n).
• Extra space complexity: O(n) for the presence array.
• Input storage: O(m) for the supplied sequence array.

Because m cannot exceed n under the program's assumptions, the overall running time is linear in n.

Common Mistakes

• Using the single-missing-number sum formula and obtaining only the sum of several missing values.
• Allocating only MAX_N presence positions but accessing index MAX_N.
• Forgetting to initialize every presence marker to zero.
• Using an input value as an index before checking its range.
• Ignoring duplicates and assuming that n - size always reflects distinct missing values.
• Starting the final scan at index 0 even though the sequence begins at 1.
• Assuming the supplied values must be sorted.

By marking each supplied value and scanning the complete expected range, the program finds every missing number in linear time and prints the results in ascending order.