Deleting two adjacent elements and replacing them with a single element from a vector

Question

So i want to find two adjacent elements(last and first are adjacent) from a vector such that their sum is minimum and after replace them with a single element=their sum. This should be done until one element remains.

I wrote a function to find the smallest adjacent pair and return the lower index. Then moved all the elements after that index one place and used a.resize(n-1). The code doesn't work and I guess the main problem is comparing last and first.

int index(vector<int> a)
{
int idx=0; int ans=100; int sum=0;
for (int i = 0; i < a.size(); ++i)
{
    sum=a[i]+a[i+1];
    if(sum<ans)
        idx=i;
}
if(a[0]+a[a.size()-1]<ans)
    idx=a.size()-1;
return idx;
}
//in main function
for (int i = 0; i < n-1; ++i)
    {
        int idx=index(a);
        if(idx==a.size()-1)
            {a[0]=a[0]+a[a.size()-1];
                ans+=a[0]+a[a.size()-1];
                a.pop_back();
            }
        else
        {
            a[idx]=a[idx]+a[idx+1];
            ans+=a[idx]+a[idx+1];
            a.erase(a.begin()+idx-1);

        }

Answer 1

Here is my solution.

Since the array is circular, each element in the array may be the first of the adjacent pair with the smallest sum.

So consider each element at index i, and its pair at index j which is (i + 1) % n to find the smallest pair. ...where n is the current number of elements in the vector. The % n will take care of the wraparound, and circular nature of your array. When i is the last element (n - 1), then j will be the first element (0).

Once the indices i and j of the smallest pair have been determined, replace one of the two elements with the sum, and erase the other one. The convention you apply will determine whether the sum of the first and last elements will be placed at the start or end of the vector.

Repeat this until there is only one element remaining.

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

// Just a handy function to display the vector.
void print(std::vector<int> const& input)
{
    std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec{ 3, 1, 4, 1, 5, 9, 2 }; // some example input data

    print(vec);
    while (vec.size() > 1) {
        // Find the smallest pair of adjacent elements.
        size_t min_i = 0;
        size_t min_j = 1;
        int min_sum = vec[0] + vec[1];
        for (size_t i = 1; i < vec.size(); ++i) {
            size_t j = (i + 1) % vec.size();
            int sum = vec[i] + vec[j];
            if (sum < min_sum) {
                min_i = i;
                min_j = j;
                min_sum = sum;
            }
        }
        // Replace element i with the sum.
        vec[min_i] = min_sum;
        // Erase element at j;
        vec.erase(vec.begin() + min_j);

        print(vec);
    }
}

Output:

3 1 4 1 5 9 2
4 4 1 5 9 2
4 5 5 9 2
5 5 9 6
10 9 6
10 15
25

---

Edit: OP asked to be shown where they went wrong.

As for your code, there are so many problems and dangerous practices. :(

First, please recall that the index [n] is not valid if there are n elements n the array. Valid indices of an array with n elements are 0 through n-1 inclusive. So accessing [i]and [i+1] when i == n-1 is a buffer overrun error because you are accessing elements n-1 (the last) and n-1 + 1, one past the last.

Your code to compute the minimum sum is incorrect in that is updates sum (which should be a local) but not ans. Write smaller functions and write unit tests for those functions. If you had written a function to compute the minimum value of the pairs of the array, you would have seen that it would have failed even the most basic of unit tests. The code you wrote does not compute the minimum.

Given an array with at least one element, finding the index of the minimum value and its index typically goes like this:

int min_val = a[0];
int min_index = 0;
for (int i = 1; i < n; ++i) {
   if (a[i] < min_val) {
      min_val = a[i];
      min_index = i;
   }
}

100 is not an appropriate initial minimum value (if that's what you intended it to be). A value like MAX_INT is better. std::numerical_limits<int>::max() is better still for modern C++.

You increment ans in a loop, which retained a value from the previous usage in the previous loop. Also, ans is not used hereafter in your program. I suggest you judiciously apply the most restrictive scope possible to your local variables.

You are special casing your wraparound by writing duplicate code with logical checks, which increases the number of opportunities you have to introduce a bug, when instead you should make use of the modulus operator to distill the code path into a single path of execution that handles both the wraparound and nominal cases of adjacency.

And finally, all your algorithm does is compute the sum of an array and store it in a single element. The approach of removing elements one at a time with erase is a performance disaster compared to a direct sum computation. I'm honouring your request to do it this way because of your "reason", which you didn't disclose, and I still find highly unjustifiable and dubious at this point, unless it's just a learning exercise.

Answer 2

You can use the following algorithm:

• Assign one of the elements to be replaced with the new value.
• Erase the other one.