Find the missing element in vector

Question

I'm solving this simple challenge:

Given a vector A with N unique elements greater than 0 and lower or equal than N+1, find the missing element. Example:

A = [1,3,2,5] -> missing number 4

A = [1,3,5,4] -> missing number 2

I've come to the following solution. I'm interested in thoughts and ideas on how to write it as expressive as possible:

Option 1, compact but not very expressive:

int solution_1(std::vector<int> &v) {
    sort(v.begin(), v.end());
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (v[i] != i+1) return i+1;
    }
    return v.size()+1;
}

Option 2

int solution_2(std::vector<int> &v) {
    sort(v.begin(), v.end());
    auto missing_element = std::find_if( 
        v.begin(), v.end(), 
        [index=1](auto& element) mutable { 
            if (element != index++) {
                return true;
            } else {
                return false;
            }
        });
    if (missing_element == v.end()) {
        return v.size() + 1;
    } else {
        return *missing_element - 1;
    }
}

Any ideas on how to improve this or how to make it more expressive?

Answer 1

You dont need the sorting. The vector contains numbers 1 to (n + 1) with one number omitted. If it wasnt omitted it would sum up to (n+ 1)*(n+ 2)/ 2. Sum the vector, subtract it from the full sum And what Is left over Is the number that was omitted.

Answer 2

Ignoring the fact that there's a better algorithm based on the sum of all elements (albiet somewhat less efficient once the input is sorted), there's plenty to review in the implementation of the functions.

---

It's rude to the caller to modify the function's argument. I suggest accepting v by value, and the caller can choose whether to std::move() into the argument or whether it needs to retain its own copy.

---

This pattern:

if (condition)
    return true;
else
    return false;

can always be simplified to

return condition;

---

Solution 2 depends on the order of execution of the predicate. It might be best to make this explicit, by passing std::execution::seq as a first argument. However, I'm not convinced that this imposes the order that's required; std::find_if() just isn't going to work in a standards-guaranteed manner with a mutable predicate.

---

Both solutions miss the useful library function std::adjacent_find().

In our case, we're looking for the first element that's not followed by an element that's one higher in value:

auto const predicate = [](int a, int b){ return a + 1 != b; }
sort(v.begin(), v.end());
if (v.empty() || v.front() != 0) { return 1; }         // first element was missing
auto it = std::adjacent_find(v.begin(), v.end(), predicate);
if (it == v.end()) { --it; }                           // last element was missing
return *it + 1;

We can safely use this std::adjacent_find() with a parallel execution policy if we want.