Missing Number - C++ Solution

1. Introduction

This blog post addresses a common problem in array processing: finding the missing number in a sequence. This problem is a classic example of arithmetic progression and can be efficiently solved using a linear time algorithm.

Problem

Given an array containing n-1 distinct integers in the range from 1 to n, the task is to find the missing number. The solution should be found in linear time.

Examples:

- Input: [1, 2, 3, 4, 5, 7, 8, 9, 10]

Output: 6

- Input: [1, 2, 3, 4]

Output: 5

2. Solution Steps

1. Calculate the expected sum of the first n natural numbers using the formula n*(n+1)/2.

2. Iterate through the array and compute the sum of its elements.

3. Subtract the sum of array elements from the expected sum to find the missing number.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the missing number
int findMissingNumber(const vector<int>& nums) {
    int n = nums.size() + 1; // Since one number is missing
    int expectedSum = n * (n + 1) / 2;
    int actualSum = 0;

    // Calculate the sum of array elements
    for (int num : nums) {
        actualSum += num;
    }

    // The missing number is the difference between the expected and actual sums
    return expectedSum - actualSum;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 7, 8, 9, 10};
    cout << "Missing number: " << findMissingNumber(nums) << endl;
    return 0;
}

Output:

Missing number: 6

Explanation:

The findMissingNumber function calculates the sum of the first n natural numbers, where n is the length of the array plus one. It then iterates over the array to find the sum of its elements. The difference between the expected sum and the actual sum of array elements is the missing number. This method efficiently finds the missing number in linear time, as demonstrated in the output for the given example.