Demonstration of Scale Balancing

Question

Have the function ScaleBalancing(int vector, int vector) read vectors which will contain two elements, the first being the two positive integer weights on a balance scale (left and right sides) and the second element being a list of available weights as positive integers. Your goal is to determine if you can balance the scale by using the least amount of weights from the list, but using at most only 2 weights.

For example: if vector is ["[5, 9]", "[1, 2, 6, 7]"] then this means there is a balance scale with a weight of 5 on the left side and 9 on the right side. It is in fact possible to balance this scale by adding a 6 to the left side from the list of weights and adding a 2 to the right side. Both scales will now equal 11 and they are perfectly balanced. Your program should return a comma separated string of the weights that were used from the list in ascending order, so for this example your program should return the string 2,6

There will only ever be one unique solution and the list of available weights will not be empty. It is also possible to add two weights to only one side of the scale to balance it. If it is not possible to balance the scale then your program should return the string not possible.

How can I make improvements to my code? I also want to know if my approach was a good way to solve this problem.

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

template <typename T>
bool all_Positive(const T start, const T end) {
    T it;
    for (it = start; it != end; it++) {
        if (*it < 0) return false;
    }

    return true;
}

bool every_Num_Positive(std::vector<int> &integerWeights, std::vector<int> &availableWeights)
{
    if (all_Positive(integerWeights.begin(),integerWeights.end()) && all_Positive(availableWeights.begin(), availableWeights.end()))
    {
        return true;
    }

    return false;
}

bool check_Length(std::vector<int> &integerWeights, std::vector<int> &availableWeights)
{
    if (integerWeights.size() == 2 && !availableWeights.empty())
    {
        return true;
    }

    return false;
}

std::vector<int> find_2_Nums_That_Add_To_Difference(std::vector<int> &availableWeights, int difference)
{
    std::vector<int> result;

    for (std::size_t i = 0; i < availableWeights.size(); ++i)
    {
        for (std::size_t j = i + 1; j < availableWeights.size(); ++j)
        {
            if (availableWeights.at(i) + availableWeights.at(j) == difference)
            {
                result.push_back(availableWeights.at(i));
                result.push_back(availableWeights.at(j));
            }
        }
    }

    return result;
}

std::string find_2_Nums_That_Minus_To_Difference(std::vector<int> availableWeights, int difference)
{
    std::vector<int> possible;
    for (std::size_t i = 0; i < availableWeights.size(); ++i)
    {
        for (std::size_t j = i + 1; j < availableWeights.size(); ++j)
        {
            if (abs(availableWeights.at(i) - availableWeights.at(j)) == difference)
            {
                return std::to_string(availableWeights.at(i)) + "," + std::to_string(availableWeights.at(j));
            }
        }
    }
    return "NOT POSSIBLE";
}

std::string scale_Balancing(std::vector<int> integerWeights, std::vector<int> availableWeights)
{
    if (check_Length(integerWeights, availableWeights) && every_Num_Positive(integerWeights,availableWeights))
    {
        int difference = std::abs(integerWeights.at(1) - integerWeights.at(0));

        std::vector<int> possibleResults = find_2_Nums_That_Add_To_Difference(availableWeights, difference);

        if (std::find(availableWeights.begin(),availableWeights.end(),difference) != availableWeights.end())
        {
            return std::to_string(difference);
        }
        else if (!possibleResults.empty())
        {
            return std::to_string(possibleResults.at(0)) + "," + std::to_string(possibleResults.at(1));
        }
        else
        {
            return find_2_Nums_That_Minus_To_Difference(availableWeights, difference);
        }
    }

    return "NOT POSSIBLE";
}

Answer 1

Unnecessary includes: These

#include <algorithm>
#include <functional>
#include <numeric>

are apparently not needed.

In your function

template <typename T>
bool all_Positive(const T start, const T end) {
    T it;
    for (it = start; it != end; it++) {
        if (*it < 0) return false;
    }

    return true;
}

the test should be

        if (*it <= 0) return false;

otherwise zero would qualify as positive number. As @tinstaafl already said, verifying the input is usually not necessary for programming challenges.

The functions

std::string find_2_Nums_That_Minus_To_Difference(std::vector<int> availableWeights, int difference)
std::string scale_Balancing(std::vector<int> integerWeights, std::vector<int> availableWeights)

take the vectors as values, you probably want to pass them by reference to avoid making copies.

In scale_Balancing() a possible pair of weights adding to the difference is determined (and possibly discarded) before searching for a single weight.

It is also confusing that

std::vector<int> find_2_Nums_That_Add_To_Difference(...)

returns a vector, but

std::string find_2_Nums_That_Minus_To_Difference(...)

returns a string.

Both functions actually return a pair of integers or “nothing.” In C++17 you can use a

std::optional<std::pair<int, int>>

for that purpose. If C++17 is not available then returning a std::pair<int, int> (with { -1, -1 } indicating “not found”) would be an alternative to returning a vector.

Better (and slightly shorter) function names would be

find_pair_with_sum(std::vector<int>&nums, int sum)
find_pair_with_difference(std::vector<int>&nums, int difference)

Note that both functions can be implemented with \$ O(n) \$ complexity if the array is sorted, see for example

• Find a pair with the given difference
• Given an array A[] and a number x, check for pair in A[] with sum as x

With those changes, the main function simplifies to

std::string scale_Balancing(std::vector<int>& integerWeights, std::vector<int>& availableWeights)
{
    int difference = std::abs(integerWeights[1] - integerWeights[0]);
    sort(availableWeights.begin(), availableWeights.end());

    if (std::binary_search(availableWeights.begin(), availableWeights.end(), difference)) {
        return std::to_string(difference);
    }

    auto sum_pair = find_pair_with_sum(availableWeights, difference);
    if (sum_pair) {
        return std::to_string(sum_pair->first) + "," + std::to_string(sum_pair->second);
    }

    auto diff_pair = find_pair_with_difference(availableWeights, difference);
    if (diff_pair) {
        return std::to_string(sum_pair->first) + "," + std::to_string(sum_pair->second);
    }

    return "NOT POSSIBLE";
}

Answer 2

It looks to me that you're over thinking this a bit.

The problem statement says that each vector will have positive integers. It is very superfluous to check for that.

Always try to avoid using the concatenation operator(+) for joining strings, the stringstream is much better for that.

You run 2 nested loops twice once to check for numbers that add to difference and those that subtract to difference. My thought is use one loop and use the std::binary_search function in the algorithm header. When each weight is subtracted from the difference all you need is the absolute value of the result and check if that weight exists.

Something like this:

const string DEFAULT_MESSAGE = "NOT POSSIBLE";
typedef vector<int>::iterator iter;
string ScaleBalancing(vector<int>& scale, vector<int>& weights)
{
    stringstream ss;
    sort(scale.begin(), scale.end());
    sort(weights.begin(), weights.end());
    int difference = scale[1] - scale[0];
    iter begin = weights.begin();
    iter end = weights.end();
    if (binary_search(begin, end, difference))
    {
        return to_string(difference);
    }
    for (int i = 0; i < weights.size(); ++i)
    {
        bool isNeg = false;
        int tempDifference = difference - weights[i];
        if (tempDifference < 0)
        {
            tempDifference *= -1;
            isNeg = true;
        }
        if (tempDifference > weights.back())
        {
            return DEFAULT_MESSAGE;
        }
        if (binary_search(begin,end,tempDifference) && tempDifference!= weights[i])
        {
            if (isNeg)
            {
                ss << tempDifference << ',' << weights[i];
            }
            else
            {
                ss << weights[i] << ',' << tempDifference;
            }
            return ss.str();
        }
    }
    return DEFAULT_MESSAGE;
}