Vector custom sum

Question

I need to identify the position of a variable from an integer array who has the following properties:

• the sum of elements before this variable is equal with the sum of elements after this variable

• if the variable doesn't exist, i will show a message.

For example, if x = {1,2,4,2,1}, the result is 4 with position 2, because 1 + 2 == 2 + 1. Any suggestions? In this example it's easy

if((x[0]+x[1])==(x[3]+x[4]))
print position 2

But for n variables?

Answer 1

Well, do it in two steps:

1. Sum all elements.
2. From first to last:
   1. If the sum equals the current element, success!
   2. Subtract it twice from the sum (once for no longer being on the right, once for being on the left).

Use standard algorithms and range-for, and it's easily written:

auto first_balanced(std::span<const int> x) noexcept {
    auto balance = std::accumulate(begin(x), end(x), 0LL);
    for (auto&& n : x) {
        if (balance == n)
            return &n;
        balance -= 2 * n;
    }
    return end(x);
}

Answer 2

Trying to build a solution out of std::algorithm, n+lg n instead of n+~n/2

Warning untested code.

bool HasHalfSum(int& atIndex, const std::vector<int>& v) {
  std::vector<int> sum;
  sum.reserve(v.size);

  std::partial_sum(v.begin(), v.end(), std::back_iterator(sum));
  // 1,3,7,9,10

  int half = sum.back() / 2; // 5

  auto found = std::lower_bound(sum.begin(), sum.end(), half);

  if (found != sum.begin() && std::prev(found) == sum.back() - *found) {
    index = std::distance(sum.begin(), found);
    return true;
  }

  return false;
}

Answer 3

Here is the O(n) solution.

Keep summing in in one variable from array beginning(left_sum) and keep deducing from the sum of elements except the first one using another(right_sum). When both becomes equal break the loop and print. Otherwise, show your msg.

#include <iostream>
#include <vector>
#include <numeric>
#include <cstddef>

int main()
{
    std::vector<int> vec {1,2,4,2,1};

    int left_sum = 0;
    int right_sum = std::accumulate(vec.cbegin()+1, vec.cend(), 0);

    bool Okay = false;
    std::size_t index = 1; // start from index 1 until n-1
    for( ; index < vec.size() - 1; ++index)
    {
        left_sum += vec[index-1];
        right_sum -= vec[index];
        if(left_sum == right_sum)
        {
            Okay = true;
            break;
        }
        // in the case of array of positive integers
        // if(left_sum > right_sum) break;
    }
    (Okay) ? std::cout << vec[index] << " " << index << std::endl: std::cout << "No such case!\n";
    return 0;
 }

Answer 4

There are several ways to do this:

Brute force - n/2 passes:

• Loop through the array.
• For each element calculate the sum before and after that element.
• If they match you found the element.
• If the sum before becomes larger than the sum after, stop processing - no match found.

This is not really efficient for larger arrays.

1.5 passes:

• Calculate the sum of all elements.
• Divide that sum by 2 (half_sum).
• Start summing the elements again from the beginning until you reach half_sum.
• Check if you found a valid element or not.

Single pass (positive numbers only):

• Keep two running sums: one from the beginning (sum1) and one from the end (sum2).
• Set sum1 = first element and sum2 = last element.
• Check for the smallest of the two and add the next/previous element to that.
• Loop until the positions meet and check if the element is a valid result.

For each method you'll have to do a litlle check first to see if the array is not too small.

Special cases to consider:

• Empty array: return false
• Array with 1 element: return element
• Array with 2 nonzero elements: return false
• What with all zero's, or groups of zero's in the middle? (see Deduplicator's comment)
• Negative elements: single pass version will not work here (see Cris Luengo's comment)
• Negative elements in general: not reliable, consider +3 +1 -1 +1 -1 +3 +1 (see Deduplicator's comment)

Answer 5

Thanks for answers. I finally managed it. I used 3 for loops, and s0 is for sum before the element, and s1 is the sum after the element.

 for(i=0;i<n;i++)
    {s1=0;
    s0=0;
        for(int j=0;j<i-1;j++)
                s0=s0+v[j];
        for(int k=i;k<n;k++)
            s1=s1+v[k];
        if(s0==s1)
            {cout<<endl<<"Position i="<<i;
            x++;}

    }
    if(x==0)
        cout<<"doesnt exist";

Answer 6

It's just looping. You need to sum the elements before and after each index and just compare these two sums:

#include <iostream>
#include <vector>
#include <numeric>

int main() {

    std::vector<int> x = {1, 2, 4, 2, 1};

    for ( unsigned idx = 0; idx < x.size(); ++idx )
        if ( std::accumulate(x.begin(), x.begin() + idx, 0) == std::accumulate(x.begin() + idx + 1, x.end(), 0) )
            std::cout << idx << std::endl;

    return 0;
}