I am not able to score 100, only

**4**out

**6**test cases are passed. Please

**check**my code and find the

**mistake**I am doing.

.

.

https://www.codechef.com/viewsolution/33122242

I am not able to score 100, only

.

.

https://www.codechef.com/viewsolution/33122242

access denied to this page

Ok then code is here

#include <bits/stdc++.h>

using namespace std;

int main(){

long long n;

cin>>n;

long long a[n],i,j,s = 0;

for(i=0;i<n;i++)

cin>>a[i];

sort(a,a+n);

for(i=0;i<n-1;i++){

for(j=i+1;j<n;j++){

s += (a[j]-a[i]);

}

}

cout<<s;

return 0;

}

Is it TLE or WA? Your code seems to be strictly O(n^2).

This is the O(n log n) solution:

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long int n;
cin>>n;
long long int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
sort(arr,arr+n);
long long int sum=0;
for (int i=0; i<n; i++)
sum += i*arr[i] - (n-1-i)*arr[i];
cout<<sum<<"\n";
return 0;
}
```

But I donâ€™t know why it works? (I actually forgot , this is my own solution)

1 Like

Your code is O(n^2) which will TLE.

Let us consider the properties of |a-b|.

|a-b| is equivalent to the following pseudocode.

```
if(a>b):
return a-b
else:
return b-a
```

We want the sum of all pairs.

Let the array be A and A_i denotes the ith element of the array after sorting

(0 indexed).

We know A_i\ge A_j if i\gt j.

So |A_i - A_j| = A_i - A_j if i\gt j and it is A_j - A_i if i<j.

Let us consider how many times A_i was added and subtracted.

For all j such that j \gt i, A_i was subtracted, which is n-i-1 times, and for all j such that j<i, A_i is added, which is i times.

So the answer is

\sum iA_i - (n-i-1)A_i.

2 Likes

TLE

It is the explanation of my implementationâ€¦ You canâ€™t get TLE

Can you explain me the (sum+=â€¦) part in loop ?

Yes, I got it from there

1 Like

Thanx