2
\$\begingroup\$

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. 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},{3}
{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 here. 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?

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – gazoh Mar 25 at 8:32
  • \$\begingroup\$ @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. \$\endgroup\$ – northerner Mar 25 at 8:49
1
\$\begingroup\$

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 practise and can unexpected conflicts. see https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice

  • ceil(in.size()/2) does not do what you expect. In c++ division by an int will return an int, discarding and remainder ( i.e. 3/2 = 1 ) taking the ceil of an int then does nothing. 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 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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The for loop you show has wrong syntax. You should eliminate the second std::size_t. \$\endgroup\$ – L. F. Mar 25 at 10:34
  • \$\begingroup\$ The example you give with {1,2,6} doesn't make sense to me. The average of {1,6} is 3.5 which is 1.5 away from 2. It would be worse to split it as {1,2},{6} because the average of {1,2} is 1.5 which is 4.5 away from 6. \$\endgroup\$ – northerner Mar 25 at 10:51
  • \$\begingroup\$ @northerner looks like I can't do maths today :( I think my point still stands I'll see if I can come up with an example that works though. \$\endgroup\$ – nivag Mar 25 at 11:06

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.