7
\$\begingroup\$

Here is the description of the problem from codewars:

Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. No floats or empty arrays will be passed.

For example, when an array is passed like [19,5,42,2,77], the output should be 7.

[10,343445353,3453445,3453545353453] should return 3453455.

Hint: Do not modify the original array.

And this is my solution which passed all tests.

// Returns the index of the smallest number.
int smallest(std::vector<int> numbers) {
  int smallest = 1;
  for(int i = 0; i < numbers.size(); i++) 
  {
    if(numbers[i] < numbers[smallest]) {
      smallest = i;
    }
  }
  return smallest;
}

long sumTwoSmallestNumbers(std::vector<int> numbers)
{
  int firstIndex = smallest(numbers);
  uint64_t first = numbers[smallest(numbers)];
  numbers.erase(numbers.begin() + firstIndex);

  uint64_t second = numbers[smallest(numbers)];

  return first + second;
}

While it's fairly fast and simple I feel like there is a way to do it while only looping over the list once and the hint about not modifying it seems to suggest that.

\$\endgroup\$
6
\$\begingroup\$

It's a smallest k elements problem at its core. Solve it like one:

pair<int, int> indicesOfSmallest2(std::vector<int> numbers) {
  if(numbers.length() < 3) return make_pair(0, 1);
  int smallest = 0;
  int nextSmallest = 1;
  if(numbers[nextSmallest] < numbers[smallest]){
      nextSmallest = 0;
      smallest = 1;
  }
  for(int i = 2; i < numbers.size(); i++) 
  {
    if(numbers[i] < numbers[nextSmallest ]) {
      nextSmallest = i;
      if(numbers[nextSmallest] < numbers[smallest]){
          nextSmallest = smallest;
          smallest = i;
      }
    }
  }
  return make_pair(smallest, nextSmallest);
}
\$\endgroup\$
  • \$\begingroup\$ Ah, perfect! This is the kind of solution I thought would exist. \$\endgroup\$ – Qwertie Oct 18 '17 at 13:57
  • 3
    \$\begingroup\$ How does this ensure it only finds positive numbers? \$\endgroup\$ – Toby Speight Oct 18 '17 at 17:19
  • 1
    \$\begingroup\$ Not sure how this solves the smallest k issue. Unless you optimized it for two values. \$\endgroup\$ – Martin York Oct 18 '17 at 18:08
  • 1
    \$\begingroup\$ Doesn't this produce wrong output on {3, 1, 2}? \$\endgroup\$ – mniip Oct 18 '17 at 23:55
  • 2
    \$\begingroup\$ This assumes that smallest will always point to number equal to or less than nextSmallest. But it doesn't ensure that for the first two entries. \$\endgroup\$ – David Schwartz Oct 19 '17 at 0:11
18
\$\begingroup\$

Missing headers

This code needs to include <vector> (for std::vector<int>) and <cstdint> (for std::uint64_t).

Don't pass collections by value

The function signature int smallest(std::vector<int> numbers) makes a copy of the input vector. If we follow the hint that we shouldn't modify it, we can pass by reference:

int smallest(const std::vector<int>& numbers);

Even better would be to act like the standard algorithms, and not depend on the type of container at all:

template <typename Iter>
typename std::iterator_traits<Iter>::value_type
smallest(Iter first, Iter last);

Use the correct type for indexing

When indexing an collection, int isn't necessarily adequate. Instead you should be using std::vector<int>::size_type (which is the same as std::size_t on many implementations):

using index_t = std::vector<int>::size_type;
for (index_t i = 0;  i < numbers.size();  ++i)

Use the standard algorithms

#include <algorithm>

That gives you std::partial_sort_copy(). You can fill a two-element array with the lowest two elements:

using std::begin;
using std::end;
int first_two[2];

std::partial_sort_copy(begin(nums), end(nums),
                       begin(first_two), end(first_two));

return std::accumulate(begin(first_two), end(first_two), 0);

(Yes, std::accumulate() is overkill, but it does show how to generalize this).

\$\endgroup\$
  • \$\begingroup\$ I'm opposed to unsigned indices unless definitely necessary. I'm not alone on that either. channel9.msdn.com/Events/GoingNative/2013/… 9:50, 42:40, 1:02:50 \$\endgroup\$ – Baum mit Augen Oct 18 '17 at 22:05
  • 4
    \$\begingroup\$ @BaummitAugen - I have to disagree with you - std::array provides a suitable type for indexing, and it's churlish not to use it. Why would you want a signed type, and how would you portably choose a suitable one? And you'd have to suppress the compiler warning for the narrowing conversion when you then use a signed value in operator[]! \$\endgroup\$ – Toby Speight Oct 19 '17 at 8:42
  • \$\begingroup\$ "Why would you want a signed type?" Because the signed types implement arithmetic on the integers (in the range they can represent), which is what you want for stuff other than bit-magic. When did you ever actually want Z/2^64 arithmetic? When was an accidental wrap-around ever less of a bug than getting an accidental negative number? The latter is trivial to assert on at least. "how would you portably choose a suitable one?" Tons of choices readily available, including the difference_types members. int64_t is a useful default, too these days unless you are on tiny devices. \$\endgroup\$ – Baum mit Augen Oct 19 '17 at 10:32
  • \$\begingroup\$ "And you'd have to suppress the compiler warning for the narrowing conversion when you then use a signed value in operator[]!" That's admittedly kind of a bummer. To quote our friends from the committee from the video I linked: "They [the signed types] are wrong", "We're sorry", "As Scott would say: We were young." What's done is done, but we should not let that be a reason to needlessly pollute new code with unsigned types. \$\endgroup\$ – Baum mit Augen Oct 19 '17 at 10:37
  • \$\begingroup\$ @Baum: do you have a link to a transcript or other alternative to the video? I'm not able to install sound hardware, and it appears meaningless without. \$\endgroup\$ – Toby Speight Oct 19 '17 at 10:45
6
\$\begingroup\$

Just a small hint at defensive coding and properly reading (or negotiating) a specification:

Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 integers. [..]

According to the above specification you accept elements of type int ... What would you expect to be the result on these arrays:

  1. [-1, -2, 1, 2]
  2. [ 0, 0, 1, 2]
  3. [-1, -2, -3, -4]
  4. [ 1, -2, -3, -4]

Note that this is not (entirely) "your fault" ... Probably the one writing the specification didn't even think about negative numbers here.

Which is why you should always make sure there's no ambiguity in a specification / task statement handed to you. If you can't "re-negotiate" like in this case of some online coding task, then at least check that the assumptions you made hold up, e.g. by checking whether all (or just the smallest) numbers are actually positive.

\$\endgroup\$
4
\$\begingroup\$

it can be a lot cleaner:

long smallest2(const std::vector<int>& nums)
{
    int first_smallest = std::numeric_limits<int>::max();
    int second_smallest = first_smallest;

    for (auto&& x: nums)
    {
        if (x < first_smallest && x > 0)
        {
            second_smallest = first_smallest;
            first_smallest = x;
            continue;
        }

        if (x < second_element && x > 0)
        {
            second_smallest = x;
        }
    }

    return first_smallest + second_smallest;
}

It will probably spend most of its time in the loop, so putting a check in the beginning will not make clear difference. Also, although in small programs you will be able to get away by passing by value, when crossing library/ABI boundaries, the code will need to perform full copy.

\$\endgroup\$
  • \$\begingroup\$ The size isn't 2. The OP's post says minimum is 4 \$\endgroup\$ – smac89 Oct 18 '17 at 17:33
  • 1
    \$\begingroup\$ @smac89, thanks for noticing that. Fixed \$\endgroup\$ – Incomputable Oct 18 '17 at 17:33
  • \$\begingroup\$ Also OP's code does not modify the "original" vector since the vector is passed by value \$\endgroup\$ – smac89 Oct 18 '17 at 17:40
  • \$\begingroup\$ @smac89, yeah, I wanted to note that the hint suggested avoiding any modifications of vector. Thanks for noticing yet another bug in my reasoning. \$\endgroup\$ – Incomputable Oct 18 '17 at 17:59
  • \$\begingroup\$ You'll want to also filter out negative values since you are looking for positive numbers. Will have to search for those first two positives. \$\endgroup\$ – Snowhawk Oct 19 '17 at 6:08
3
\$\begingroup\$

I would solve it like finding the smallest k elements in a container.

This is usually done with a heap (a heap with two values is just as affective as keeping two values and comparing them with each new value).

The next thing I would note is that you are passed an array. But if I was writing a generic algorithm I would use iterators as the interface (you can then use your vector interface as a wrapper to the generic algorithm).

I see you use long to try and avoid overflow:

long sumTwoSmallestNumbers(std::vector<int> numbers)

This does not save you from overflow. I would rather keep the types the same for input and output. If I pass you a vector of int I expect the answer to be an int. Your current implementation violates the rule of least surprise.

This is how I would do it:

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <functional>
#include <iterator>


template<typename I>
int sumofsmallest(I begin, I end, int count)
{
    using value_type = typename std::iterator_traits<I>::value_type;
    using Comp       = std::less<value_type>;

    Comp                    comp;
    std::vector<value_type> smallest;
    smallest.reserve(count + 1); 

    for(;begin != end && count; --count, ++begin)
    {   
        smallest.push_back(*begin);
    }   

    // Make sure the smallest is ordered with the largest value at
    // the peak ready to be ejected.
    std::make_heap(std::begin(smallest), std::end(smallest), comp);

    for(;begin != end; ++begin)
    {   
        // Add a new value and re-sort so the largest is ready to pop
        smallest.push_back(*begin);
        push_heap(std::begin(smallest), std::end(smallest), comp);

        // Pop the largest value.
        pop_heap(std::begin(smallest), std::end(smallest), comp);
        smallest.pop_back();
    }   

    // Sum up what is left in the array.
    return std::accumulate(std::begin(smallest), std::end(smallest), 0); 
}

int sumTwoSmallestNumbers(std::vector<int> numbers)
{
    return sumofsmallest(std::begin(numbers), std::end(numbers), 2);
}

int main()
{
    std::vector<int> x{19,5,42,2,77};
    std::cout << sumofsmallest(std::begin(x), std::end(x), 2) << "\n";
}
\$\endgroup\$
  • \$\begingroup\$ I think you intended to call sumTwoSmallestNumbers rather than sumSmallest, directly. Otherwise, I see no use for sumTwoSmallestNumbers \$\endgroup\$ – smac89 Oct 18 '17 at 19:38
  • \$\begingroup\$ @smac89: Yes I see no use for sumTwoSmallestNumbers either. \$\endgroup\$ – Martin York Oct 18 '17 at 19:46
  • \$\begingroup\$ It might save a bit of shuffling to avoid pushing a new value onto the heap if it's not going to stay there (i.e. if it's larger than the current largest value). Other than that there's a style choice between your two loops and a single loop with if (count-- > 0) continue; (or if (smallest.size() < count)) before the pruning step - neither of those is obviously better than the other. \$\endgroup\$ – Toby Speight Oct 18 '17 at 20:29

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.