3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ geeksforgeeks.org/find-the-missing-number \$\endgroup\$ – Quuxplusone Jan 21 at 1:52
  • \$\begingroup\$ Your examples do not comply with your task description. Input lenght Is 4 therefore it should contain elements lower than 5. But they contain element 5. But it seems more like the task description Is a contradiction on Its own So maybe you copied the description wrong? \$\endgroup\$ – slepic Jan 21 at 6:19
  • \$\begingroup\$ Wrong task description, I meant lower or equal \$\endgroup\$ – Blasco Jan 21 at 7:42
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ But be sure that N is small enough for the sum not to overflow, or take other measures! \$\endgroup\$ – phipsgabler Jan 21 at 9:59
  • \$\begingroup\$ Might be worth pointing Blasco at std::accumulate() for the actual summing. \$\endgroup\$ – Toby Speight Jan 21 at 11:33
  • 5
    \$\begingroup\$ @phipsgabler, I've just thought about it a bit further; if we calculate using an unsigned type large enough to represent N, then overflow should just cancel out and not be a problem. \$\endgroup\$ – Toby Speight Jan 21 at 14:00
  • \$\begingroup\$ Oh yeah, I have much too bad an intuition for number theory, but I realize it now. \$\endgroup\$ – phipsgabler Jan 21 at 14:27
  • 2
    \$\begingroup\$ @phipsgabler, it does need some care, because of the division. We need to subtract twice the sum from twice the expected sum, and divide that by two, or be cleverer about computing the expected sum by halving one of the arguments before the multiplication. \$\endgroup\$ – Toby Speight Jan 21 at 15:12
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.