Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Number of values in a vector that add up to a sum S

I have the following task:

Write the function that has the header:long long CountSumS(vector &a, int s)

The function will return the number of pairs with (a[i], a[j]); i < j; a[i] + a[j] = s)
Example:
If a = (8, 2, 3, 8, 7, 5) and s = 10, the function will return 3, the pairs being (8, 2), (2, 8) and (3, 7)

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

I’m also trying to do this efficiently, so simply taking every other element and checking the sum of all the values after it isn’t the solution I’m looking for.

I tried solving this using an unordered multimap and I have the following function:

long long CountSumS(vector<int>& v, int sum)
{
    int cnt = 0;
    typedef unordered_multimap<int, int>::iterator iter;
    unordered_multimap<int, int> m;

    for (int i = 0; i < v.size(); i++)
        m.insert(make_pair(v[i], i));

    for (int i = 0; i < v.size(); i++)
    {
        int x = sum - v[i];
        //the needed value to make the sum

        pair<iter, iter> result = m.equal_range(x);
        int count = distance(result.first, result.second);

        if (count != 0)
        {
            for (auto iter = result.first; iter != result.second; iter ++) //iterates through the values 
            {
                if (iter->second > i)
                    cnt++;
                /*else
                    iter = m.erase(iter);*/
            }
        }
    }
    return cnt;

It solves the problem inefficiently because after all it just checks through all elements with a certain key, so the solution I thought of was to delete all elements in the map that have value smaller than "i", since it means the element has already been passed in the vector and I can’t use it to form a sum anyway. The section written in the /**/ was my approach at trying to erase the value at that iterator, but I get an error when I tried to run the code (image)(https://i.stack.imgur.com/Nl3SI.png). I was wondering what was causing that error.

I appreciate all input on a better aproach for an easier solution, it was just the first thing I could think of and tried to implement.

>Solution :

Using iter ++ after iter = m.erase(iter) may result in an iterator overrun.

Do only one of them in each iteration.

            for (auto iter = result.first; iter != result.second; ) //iterates through the values 
            {
                if (iter->second > i)
                {
                    cnt++;
                    iter++;
                }
                else
                    iter = m.erase(iter);
            }
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading