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
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