Splitting a list so the two resulting lists have the same average

Question

Problem Description:

The purpose of this function is to take a list of sorted numbers and split it into two evenly balanced lists. By evenly balanced I mean the numbers in the two lists have as close as possible to an equal average while as close as possible in length. Put simply, the resulting lists should have the same number of large numbers as small numbers. The algorithm I use is to remove the largest and smallest numbers from the input list and add alternate appending them to an output list. I am open to other algorithms.

Assumptions:

• input list is sorted in ascending order
• all values in list are greater than 0
• there are no duplicates in list
• the input list will be at least 3 elements long
• it is likely that adjacent elements in the input list will differ by very little. For example it's unlikely to have {1,2,500} and is much more likely to be {1,2,5}

Correct Examples:

{2,4,5,9}=>{2,9},{4,5}
{1,2,3}=>{1,3},{2}
{1,2,3,4,5,6}=>{1,6,3},{2,5,4}
{1,2,3,4,5,6}=>{2,6,3},{1,5,4}

Incorrect Examples:

{1,2,3,4,5,6}=>{1,2,3},{4,5,6}
{2,4,5,9}=>{2,4},{5,9}

The Code:

#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>

using namespace std;

/*prototypes*/
void splitInTwo(vector<int> in, vector<int> &out1, vector<int> &out2);//should the last two be past by const reference? 
void displayContents(const vector<int> in);


int main()
{
    cout << "program started" << endl;
    vector<int>a = {2,3,4,5,6,7,8,10};
    vector<int>b = {2,3,5,7,8,12,20,40};
    vector<int>c = {1,2,3};
    vector<int>d = {10, 15, 33};
    vector<int>e = {10, 20, 30, 40, 50, 60, 70};
    vector<int>f = {1,2,3,4,5,6};
    vector<int>g = {1,2,3,4,5,6,7,8,9,10};
    vector<int>h = {1,2,3,4,5,6,7,8,9,10,11,12};
    vector<int>i = {1,2,3,4,5,6,7,8,9,10,11,12,13};
    vector<int>j = {1,2,3,4,5,6,7,8,9,10,11,12,14};
    
    vector<int> out1, out2;

    splitInTwo(a, out1, out2);
    splitInTwo(b, out1, out2);
    splitInTwo(c, out1, out2);
    splitInTwo(d, out1, out2);
    splitInTwo(e, out1, out2);
    splitInTwo(f, out1, out2);
    splitInTwo(g, out1, out2);
    splitInTwo(h, out1, out2);
    splitInTwo(i, out1, out2);
    splitInTwo(j, out1, out2);

    return 0;
}

void splitInTwo(vector<int> in, vector<int> &out1, vector<int> &out2)
{
    out1.clear();
    out2.clear();
    out1.reserve(ceil(in.size()/2));
    out2.reserve(floor(in.size()/2));
    bool alternate = true;
    for(int i = 0, j = in.size() - 1; i <= j; i++, j--)//why exactly doesn't auto work here?
    {
        if(i == j)//i and j point to same element
        {
            if(alternate)
            {
                out1.push_back(in[i]);
            }
            else
            {
                out2.push_back(in[i]);
            }
        }
        else if(j - i == 1)//j and i point to adjacent elements
        {
            if(out1.size() < out2.size())
            {
                out1.push_back(in[i]);
                out1.push_back(in[j]);
            }
            else if(out1.size() > out2.size())
            {
                out2.push_back(in[i]);
                out2.push_back(in[j]);
            }
            else//equal size
            {           
                out1.push_back(in[i]);
                out2.push_back(in[j]);
            }
            break;
        }

        else if(alternate)
        {
            out1.push_back(in[i]);
            out1.push_back(in[j]);
        }
        else
        {
            out2.push_back(in[i]);
            out2.push_back(in[j]);
        }
        alternate = !alternate;//NB operator is not !=
    }
    
    assert(out1.size() - out2.size() <= 1 && "incorrect length of return vector");
    
    //for testing only
    cout << "in: " << endl;
    displayContents(in);
    cout << "out: " << endl;
    displayContents(out1);
    displayContents(out2);
}

void displayContents(const vector<int> in)
{
    for(auto i : in)
        cout << i << ", ";
    cout << "\n";
}

Specific Question:

I had initially thought the problem was a lot simpler to solve. It would be nice to remove some of the variables or nested if-statements from the code. In the outer for loop, I'm curious why auto couldn't be used? I guess it's because the literal 0 is an int and size() returns an unsigned int?

Since I thought the problem was simpler to solve, some aspects of the code did not scale well. For example I wish I put all the test cases in an array. Any feedback regarding the unit testing or overall design principles? Any feedback at all is welcome, I would like to optimize this a learning experience :)

Similar work:

There is a similar problem at GeeksForGeeks: find index such that total of elements to the left is "right total". However this is different because the input list need not be sorted. In the analysis of their "Efficient solution" they give "time complexity" as O(n). Mine I believe to have the runtime of θ(n/2). Is this correct? In this context isn't it more correct to discuss runtime than time complexity?

Answer 1

I'll look at the current code first then look at algorithmic issues.

• Avoid using namespace std — while it probably won't cause issues in a small project like this it is bad practice and can unexpected conflicts. See Why is "using namespace std;" considered bad practice?.

• ceil(in.size()/2) does not do what you expect. In C++, division by an integer will return an integer, discarding and remainder (e.g. 3/2 = 1), and ceil() will return the same integer value. I would replace those lines, using the modulus, with

  out1.reserve((in.size()/2) + in.size()%2);
  out2.reserve(in.size()/2);
  

• You can't currently use auto in your for loop as i and j would have different types. size() returns a type of std::size_t (which is an unsigned integer type) where 0 is signed. Also in general you should prefer unsigned values for indices in a loop as they are always greater than 0.

• Your for loop is correct, but personally I would write it with only 1 value like this. I find that easier to read, but is mainly a matter of taste.

  for(std::size_t i = 0, mid = in.size()/2 + in.size()%2; i < mid; i++ )
  {
      size_t j = in.size() - i - 1;
  }
  

In terms of the algorithm, despite what I initially thought I can't actually find an example where this approach doesn't work. So nice job on that count.