C++ Program to Find Missing Number in Array

You can find the missing number in an array of size n containing numbers from 1 to n+1 by calculating the expected sum with n*(n+1)/2 and subtracting the actual sum of array elements; in C++, this can be done with int missing = total_sum - actual_sum;.

Examples

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

Output3

InputArray: [2, 3, 1, 5]

Output4

InputArray: [1]

Output2

How to Think About It

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

Algorithm

1

Get the size of the array as n.

2

Calculate the expected total sum of numbers from 1 to n+1 using the formula.

3

Calculate the sum of all elements in the given array.

4

Subtract the actual sum from the expected total sum to find the missing number.

5

Return or print the missing number.

Code

cpp

#include <iostream>
#include <vector>

int findMissingNumber(const std::vector<int>& arr) {
    int n = arr.size() + 1;
    int total_sum = n * (n + 1) / 2;
    int actual_sum = 0;
    for (int num : arr) {
        actual_sum += num;
    }
    return total_sum - actual_sum;
}

int main() {
    std::vector<int> arr = {1, 2, 4, 5, 6};
    std::cout << "Missing number is: " << findMissingNumber(arr) << std::endl;
    return 0;
}

Output

Missing number is: 3

Dry Run

Let's trace the array [1, 2, 4, 5, 6] through the code

1

Calculate n

Array size is 5, so n = 5 + 1 = 6

2

Calculate total_sum

total_sum = 6 * (6 + 1) / 2 = 6 * 7 / 2 = 21

3

Calculate actual_sum

Sum of array elements = 1 + 2 + 4 + 5 + 6 = 18

4

Find missing number

missing = total_sum - actual_sum = 21 - 18 = 3

Step	Value
n	6
total_sum	21
actual_sum	18
missing	3

Why This Works

Step 1: Calculate expected sum

The formula n*(n+1)/2 gives the sum of all numbers from 1 to n, which is the total if no number was missing.

Step 2: Sum array elements

Adding all elements in the array gives the actual sum present.

Step 3: Subtract to find missing

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

Alternative Approaches

Using XOR operation

cpp

#include <iostream>
#include <vector>

int findMissingXOR(const std::vector<int>& arr) {
    int n = arr.size() + 1;
    int xor_all = 0;
    for (int i = 1; i <= n; ++i) {
        xor_all ^= i;
    }
    int xor_arr = 0;
    for (int num : arr) {
        xor_arr ^= num;
    }
    return xor_all ^ xor_arr;
}

int main() {
    std::vector<int> arr = {1, 2, 4, 5, 6};
    std::cout << "Missing number is: " << findMissingXOR(arr) << std::endl;
    return 0;
}

XOR method uses bitwise operations and avoids overflow risk but is less intuitive than sum formula.

Using boolean visited array

cpp

#include <iostream>
#include <vector>

int findMissingVisited(const std::vector<int>& arr) {
    int n = arr.size() + 1;
    std::vector<bool> visited(n + 1, false);
    for (int num : arr) {
        visited[num] = true;
    }
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) return i;
    }
    return -1; // Should not happen
}

int main() {
    std::vector<int> arr = {1, 2, 4, 5, 6};
    std::cout << "Missing number is: " << findMissingVisited(arr) << std::endl;
    return 0;
}

This method uses extra space but is straightforward and easy to understand.

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

Time Complexity

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

Space Complexity

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

Which Approach is Fastest?

The sum formula and XOR methods both run in O(n) time and O(1) space, but the sum formula is simpler and more readable.

Approach	Time	Space	Best For
Sum Formula	O(n)	O(1)	Simple and fast for integer ranges
XOR Operation	O(n)	O(1)	Avoids overflow, uses bitwise logic
Visited Array	O(n)	O(n)	Easy to understand, uses extra memory