Sum of the two lowest positive numbers in a vector

Question

I made a function sumOfTwoSmallestNumbers() that takes an integer vector (containing only positive values) and it returns the sum of the two lowest positive numbers stored in that vector. Unfortunately, my function fails for a few test cases (I do not have access to the inputs of those test cases). Please help me find the error in my code. NOTE: Vector always consists of a minimum of 4 positive values

#include <iostream>
#include <vector>

using namespace std;

long sumOfTwoSmallestNumbers (vector<int> numbers)
{
  long int sum = 0;
  long int min1 = numbers[0];
  int position;
  for (unsigned long int i = 0; i < numbers.size(); i++){ 
    if (numbers[i] < min1){
      min1 = numbers[i];
      position = i;
    }
  }
  numbers.erase(numbers.begin() + position - 1);
  long int min2 = numbers[0];
  for (unsigned long int i = 0; i < numbers.size(); i++){ 
    if (numbers[i] < min2){
      min2 = numbers[i];
    }
  }
  sum = min1 + min2;
  return sum;
}

Logic: I have tried to first find the smallest value and store it in a variable and then remove that value from the vector. After that, I again searched for the smallest value in the vector and stored it in a variable. In end, I have added the two values and returned the sum.

Answer 1

What do you think of this:

// Simple function that will swap smallest with next_smallest
// if smallest > next_smallest. Returns true if a swap happened
bool TwoItemSort(int& smallest, int& next_smallest)
{
    if (next_smallest < smallest)
    {
        int tmp = smallest;
        smallest = next_smallest;
        next_smallest = tmp;
        return true;
    }
    return false;
}

long sumOfTwoSmallestNumbers(const vector<int>& numbers)
{
    if (numbers.size() < 2)
    {
        return 0;
    }

    int smallest = numbers[0];
    int nextsmallest = numbers[1];

    TwoItemSort(smallest, nextsmallest);

    for (size_t i = 2; i < numbers.size(); i++)
    {
        int value = numbers[i];
        if (TwoItemSort(nextsmallest, value))
        {
            TwoItemSort(smallest, nextsmallest);
        }
    }

    return smallest + nextsmallest;
}

Answer 2

Your code has a couple of issues:

1. If the smallest number in the vector is the first, position will be uninitialized and cause UB (Undefined Behavior).
2. If you'll initiazlie position to 0 as required, then again if the smallest number in the vector is the first, this line numbers.erase(numbers.begin() + position - 1) will attempt to use an iterator to before numbers.begin(). This is invalid.

My solution below only keeps track of smallest and secondSmallest without having to modify the vector at all (and thus I can pass it by const&). It also requires only one traverse of the vector (and the complexity is O(n)).

#include <iostream>
#include <vector>
#include <assert.h>

long sumOfTwoSmallestNumbers(std::vector<int> const & numbers)
{
    assert(numbers.size() >= 4);   // The OP specified that in the question.
    int smallest =       (numbers[0] < numbers[1]) ? numbers[0] : numbers[1];
    int secondSmallest = (numbers[0] < numbers[1]) ? numbers[1] : numbers[0];
    for (size_t i = 2; i < numbers.size(); ++i)
    {
        if (numbers[i] < smallest)
        {
            // Need to update both:
            secondSmallest = smallest;
            smallest = numbers[i];
        }
        else if (numbers[i] < secondSmallest)
        {
            // Need to update only second:
            secondSmallest = numbers[i];
        }
    }
    return (smallest + secondSmallest);

}

int main()
{
    std::vector<int> v = { 1,4,7,2 };
    auto s = sumOfTwoSmallestNumbers(v);
    std::cout << "sumOfTwoSmallestNumbers: " << s << std::endl;
    return 0;
}

Output:

sumOfTwoSmallestNumbers: 3

A side note: it's better to avoid using namespace std - see here Why is "using namespace std;" considered bad practice?.

Answer 3

um, this is a two-liner...

std::sort(vec.begin(),vec.end());
auto sum = vec.at(0) + vec.at(1);

---

Hope this helps

---

Caveat: it does not skip negative numbers, but that has been left out as a learning exercise for the OP.

Answer 4

#include <bits/stdc++.h>

using namespace std;

int sumOfSmallestPositive(vector<int> arr);

int main()
{

     vector<int> arr{-8,-24,14,-56,-1,5,87,12,-10,11};
     cout<<sumOfSmallestPositive(arr);
     return 0;
}


int sumOfSmallestPositive(vector<int> arr)
{
    sort(arr.begin(),arr.end());
    pair<int,int> p;
    for(int i=0;i<arr.size();i++)
    {
        if(arr[i]>0)
        {
            p.first=arr[i];
            p.second=0;
            if(i+1<=arr.size()-1)
                p.second=arr[i+1];
            break;
        }
    }
    return p.first +p.second;  //return 5+11=16
}