The Algorithm Design Manual (3rd) Exercise Solution 'E2-39'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 2-39

Question

An unsorted array of size n contains distinct integers between $1$ and $n + 1$, with one element missing. Give an $O(n)$ algorithm to find the missing integer, without using any extra space.

Solution

C++ code with explanation comments.

#include <vector>
int find_missing(const std::vector<int>& missing_array) {
    int n{(int)missing_array.size()};

    // calc sum of not-missing array using summation formula
    int desired_sum = (n + 1) * (n + 2) / 2;

    // sum one by one from the array
    // O(n)
    int current_sum{0};
    for (int i = 0; i < n; i++) {
        current_sum += missing_array[i];
    }

    return desired_sum - current_sum;
}