-2
Input:4
Input: 4 2 3 6
Output :29

Explanation:

  • sort the array and then add 2+3=5 now we have 5 4 6
  • Next we add 5+4=9 now we have 9 and 6
  • next we add 9+6=15 and finally we return 29 as solution which is sum of 5+9+15=29

I have to write a code for the same.

Here is my code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int num;
    cin >> num;
    vector<int> box;
    for (int i = 0; i < num; i++)
    {
        int temp;
        cin >> temp;
        box.push_back(temp);
    }
    sort(box.begin(), box.end());
    vector<int> res;
    int sum = box[0];
    if (box.size() == 1)
    {
        cout << sum;
    }
    else
    {
        for (int i = 1; i < box.size(); i++)
        {
            sum = sum + box[i];
            res[i] = sum;
        }
        res[0] = 0;
        int result = 0;
        for (int i = 0; i < res.size(); i++)
        {
            result += res[i];
        }
        cout << result;
    }
}

The code is not working properly and is running into errors can someone help..? The question seems to be simple but I am unable to come up with and efficient solution for the same.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
Adarsh Pandey
  • 57
  • 1
  • 1
  • 4
  • 5
    `vector res(num);` res is empty when you call `[]`. – rafix07 Oct 04 '18 at 10:49
  • 4
    Not related to your question, but the dual combo of [`bits/stdc++.h`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) is a very bad idea. Matter of fact, better avoid both. – StoryTeller - Unslander Monica Oct 04 '18 at 10:50
  • 1
    Please do not upload images of text, instead, copy the text itself here. Links can go bad, some employers block images at all and most important: if the image is of code we cannot copy the code to our own IDE. So please, copy the text of your problem statement instead of posting a picture of it. Also, please do elaborate on "not working properly". Add the error messages and line numbers at the very least, so we know what to look for. – Adriaan Oct 04 '18 at 11:34
  • this looks like a competitive problem/problem from some algorithm problem website. Can you post a link to the original source if that is the case? Otherwise can you share limits for the number of values being entered and their magnitude? – Ivaylo Strandjev Oct 04 '18 at 12:17

1 Answers1

1

Given the sorted vector<int> box, the value you're looking for could be assigned to foo like this:

foo += box[0] + box[1];
foo += box[0] + box[1] + box[2];
foo += box[0] + box[1] + box[2] + box[3];

It's pretty clear that for a given zero based element index i it will be added to foo, size(box) - i times (with the exception of the first element which will be added size(box) - 1 times.) So you could very simply write the logic like this:

auto foo = box.front() * (size(box) - 1);

for(auto i = 1; i < size(box); ++i) {
    foo += box[i] * (size(box) - i);
}

This obviously expects that there will be at least 2 elements in box (and if box is empty this is even undefined.) So obviously this needs to be wrapped in an if-check. Anyway, if you trust in accumulate to take your mutable lambda correctly you can just directly return this sum like this:

accumulate(next(cbegin(box)), cend(box), box.front() * (size(box) - 1), [i = size(box)](const auto lhs, const auto rhs) mutable { return lhs + rhs * --i; })

Live Example

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288