Please help me to solve this problem in O(n)

For a sequence of integers [a1,a2,…an], define the function f(i) as follows: Take the first i elements of a (a1,a2,…ai) and sort them in non-decreasing order. Call this new sequence si. Let f(i) = 1 * s1 + 2 * s2 + …i * si.

Given a sequence of n integers, sort them in non-decreasing order then compute f(1) + f(2) + …+ f(n). As result may be very large, return it modulo(1e9+7).

Constraints : 1 <= n <= 10^6, 1<=a[i] <= 10^6.

Example :

Input:

n=3, a = [9, 5, 8]

Output: 80

Explanation :

s1 = [9]; f(1) = 1 * 9=9.

s2 = [5, 9]; f(2) = 1 * 5 + 2 * 9 = 23.

s3 = [5,8,9]; f(3) = 1 * 5 + 2 * 8 + 3 * 9 = 48.

f(1)+f(2)+…+f(n) = f(1)+f(2)+f(3) = 9+23+48=80.

My Logic :

long long solve(vector a)
{  

    long long count=0, n=a.size(), sum=0;

    for(long long i=0; i<n; i++)
    {   
        sort(a.begin(), a.begin()+count+1);
        count++;

        for(long long j=0; j<count; j++)
        sum+=a[j]*(j+1);
     }

     return sum;
}
1 Like

As always said, you should provide a link to the problem statement and it’s also highly recommended that you discuss your intended approach or the point you are stuck with

4 Likes

Nice Problem…Plz share the source of this problem…

I don’t know the source. Can you please optimize my code? Kindly share if you find different solution.

I can only wonder why you are trying so hard to hide this post with copy paste of irrelevant details on stack and asking moderators to “change content”.

I’m genuinely curious. What about this post is so incriminating that you need to try so hard to hide it?

1 Like

Then who gave you this problem?? Also your current code cannot be optimized…Currently I can just say that you should try to find a relation between f(i) and f(i+1) in O(1) or O(log(n))

I am a beginner. I don’t know the source, but i assure you that i hiding because you asked me to give source then only i can share my problem. Nothing more than that.

I think in my college contest. Thanks for the idea.

1 Like

Anyways it cannot be solved in O(n) Or perhaps I’m not smart enough.

Just compute \sum a_i \times (i+1) \times (n-i).

It’s easy to see that this is the answer because each term will always have i elements less than it so it’s weight will be i+1, and will be present in n-i prefixes.

1 Like

Can you give example of your logic as i am getting wrong answer.

Can you tell where are you checking your answer?? You said before you don’t have the link…

3 Likes

sahi pakre ho

First of all, thanks for reply. According to the logic suggest by everule1, i am getting wrong answer. You asked me where i am checking my answer is in my rough copy and getting wrong answer. I want to clarify that i am not doing any type of cheating and all but just asking my doubt. If you really want to help me then suggest me logic. If you are not interested in it then please don’t comment and if you think i am cheating then just flag my post.

Can you share the link of the college contest?

I forgot to mention you have to sort first. That’s why its O(n\log{n})

I don’t have a link. Why you asking me the link again n again. If you not interested please don’t reply to me.

I think O(n) is not possible.

I have seen this problem on hackerrank challange recently. Got TLE in 5 test cases on brute force solution O(N * K * Log(K) )

I have thought of O( N ^ 2 ) solution but not sure if it will pass the TLE.

i think fenwick tree might help u

Can you explain your logic further because I am unable to understand it