C Program to find the missing number from a sequence

Suppose a sequence should contain every integer from 1 through n, but exactly one number is missing. If the remaining n - 1 values are stored in an array, the missing number can be found by comparing the expected sum with the actual sum.

For example:

Complete sequence: 1 2 3 4 5 6 7 8
Given array:       3 7 1 8 2 5 4
Missing number:    6

The values may appear in any order. They do not need to be sorted.

Assumptions

The program solves the standard single-missing-number problem under these conditions:

• The complete sequence is 1, 2, 3, ..., n.
• The array contains n - 1 values.
• Exactly one value is missing.
• Every supplied value is distinct and lies between 1 and n.

If duplicates, out-of-range values, or multiple missing numbers are allowed, a different validation strategy is required.

C Program to Find the Missing Number from 1 to n

#include <stdio.h>

#define MAX_N 100

int main(void) {
    int sequence[MAX_N];
    int n;
    long long actualSum = 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 %d distinct elements from 1 to %d:\n", n - 1, n);
    for (int index = 0; index < n - 1; index++) {
        if (scanf("%d", &sequence[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }

        actualSum += sequence[index];
    }

    long long expectedSum = (long long)n * (n + 1) / 2;
    long long missingNumber = expectedSum - actualSum;

    printf("The missing number is: %lld\n", missingNumber);

    return 0;
}

Sample Output

Enter the upper limit n: 8
Enter 7 distinct elements from 1 to 8:
3 7 1 8 2 5 4
The missing number is: 6

How the Program Works

The sum of every integer from 1 through n is:

expected sum = n × (n + 1) / 2

The program also adds the n - 1 values that are actually present. Because exactly one number is absent, subtracting the actual sum from the expected sum gives that number:

missing number = expected sum - actual sum

The input loop calculates actualSum as the values are read, so another pass over the array is unnecessary.

Dry Run

For n = 8, the expected sum is:

8 × 9 / 2 = 36

Now add the supplied values:

Value read	Running actual sum
3	3
7	10
1	11
8	19
2	21
5	26
4	30

Finally:

missing number = 36 - 30
               = 6

Why Does the Input Order Not Matter?

Addition is independent of order. The arrays below have the same sum and therefore produce the same missing number:

1 2 3 5 6
6 3 1 5 2

Both contain the values from 1 to 6 except 4. Sorting the input before calculating the sum would add unnecessary work.

Why Use long long for the Sums?

The expression n * (n + 1) grows much faster than n. With large limits, it can exceed the range of an int even when the final missing value is small.

The cast is deliberately applied before multiplication:

(long long)n * (n + 1) / 2

This makes C perform the multiplication using long long arithmetic. Writing the cast after the multiplication would be too late if integer overflow had already occurred.

The sample program limits n to 100, but using the wider type is still a good habit and makes the formula safer if that limit is increased later.

What If the First Number Is Missing?

The same formula handles a missing boundary value:

n = 5
Array: 2 3 4 5
Expected sum: 15
Actual sum:   14
Missing:       1

What If n Is Missing?

No special case is needed:

n = 5
Array: 1 2 3 4
Expected sum: 15
Actual sum:   10
Missing:       5

What Happens When n Is 1?

The complete sequence contains only the number 1, and the input array contains n - 1, or zero, elements. The actual sum remains 0, so the result is:

expected sum = 1
actual sum   = 0
missing      = 1

The reading loop simply performs no iterations.

Why Must the Values Be Distinct?

The sum method depends on the actual array containing every expected value except one. A duplicate replaces another value and changes the sum in a way that may produce an invalid result.

For example, with n = 5:

Invalid array: 1 2 2 5

Both 3 and 4 are absent, while 2 appears twice. There is no single missing number, so the assumptions have been violated.

When input cannot be trusted, use a frequency array or another validation structure to detect duplicates and out-of-range values before reporting a result.

XOR Alternative Without Addition

The bitwise XOR operator can find the same missing value without calculating a potentially large sum:

int missingNumber = 0;

for (int number = 1; number <= n; number++) {
    missingNumber ^= number;
}

for (int index = 0; index < n - 1; index++) {
    missingNumber ^= sequence[index];
}

XOR has these useful properties:

x ^ x = 0
x ^ 0 = x

Every number that occurs in both the complete sequence and the array cancels itself. Only the missing number remains. This method runs in O(n) time, uses O(1) extra space, and avoids arithmetic overflow, although the sum method is often easier for beginners to understand.

Alternative Approaches

• Sorting: Sort the array and compare each value with the expected number. This usually takes O(n log n) time and may change the array.
• Frequency array: Mark each supplied value as present, then scan from 1 to n. This can validate duplicates and ranges but needs O(n) extra space.
• Boolean lookup table: Similar to a frequency array when only presence or absence matters.
• Brute-force search: Search the entire array for every number from 1 to n. This uses constant extra space but takes O(n²) time.

What If the Sequence Starts Somewhere Other Than 1?

For a consecutive sequence from first through last, the expected sum is:

expected sum = (first + last) × number of terms / 2

The number of terms is last - first + 1. Subtracting the sum of the supplied values still reveals one missing number, provided all other assumptions remain true.

What If More Than One Number Is Missing?

The difference between the expected and actual sums would give only the sum of all missing numbers. It would not identify each one individually.

For example, if 3 and 7 are missing, the difference is 10, but that does not prove which two values produced it. Multiple missing values require another approach, such as a presence array, sorting, or additional mathematical information.

Time and Space Complexity

For the sequence 1 through n:

• Time complexity: O(n) because the program reads and adds each of the n - 1 supplied values once.
• Extra space complexity for the algorithm: O(1) because only sum variables are required. The input array itself uses O(n) storage.

The array could be omitted entirely if the values are needed only for their sum, but it is retained here to demonstrate the standard array-based problem.

Common Mistakes

• Reading n values even though an array with one missing value contains only n - 1 elements.
• Using the formula n * (n - 1) / 2 instead of n * (n + 1) / 2.
• Performing the multiplication as int before converting the result to long long.
• Assuming the array must be sorted.
• Ignoring duplicates, out-of-range values, or multiple missing numbers.
• Using this exact formula for a sequence that does not begin at 1.
• Subtracting in the wrong direction and producing a negative result.

By subtracting the sum of the supplied values from the expected sum of 1 through n, the program finds the single missing number in linear time without sorting the array.