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

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?

• I think your definition of "evenly balanced" need some clarification. Consider the list {1, 100, 101, 102}, which fits your assumptions. Your algorithm would yield {1, 102}, {100, 101}, with averages 49 apart. The solution {1, 101, 102}, {100} is better considering their 32 average difference, but can they be considered "balanced" as their lengths differ more? Commented Mar 25, 2020 at 8:32
• @gazoh you make a good point. Typically the difference between adjacent elements wont be very big (i.e. 99% of the time less than 20). I had constructed the algorithm so that the resulting lists are of the same size, or differ by 1. That being said, if you can think of a better algorithm please share. Commented Mar 25, 2020 at 8:49
• A sequence like 1 3 4 6 7 9 13 15 19 21 25 100 101 103 104 106 107 109 113 115 119 121 is bound to highlight problems with simplistic approaches. If the parts were to have about equal lengths, I'd go for • compute average value for a pair • for pairs from outside in: • append to part with lower total if above average, and vice-versa - and fail for #pairs not even… Commented Nov 3, 2021 at 2:38
• Very similar problem: Divide list into two equal parts Commented Nov 3, 2021 at 7:34
• en.wikipedia: Two-way balanced partitioning (going for same sum: adapt by adding dummies of average value) (deleted an answer where I seem to have re-invented one of those wheels). Commented Nov 3, 2021 at 8:16

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.

• Contraindications: ES.107, [ES.102]. Don't use an unsigned type because it won't be negative. Only use unsigned types when you are doing bit manipulation or require the wrap-around behavior. Commented Nov 2, 2021 at 14:47
• (auto j = in.size() - 1, i = j - j ?) Commented Nov 3, 2021 at 2:36