Utkarsh and LCM

Is the given array is already sorted??? http://www.codechef.com/DBYZ15/problems/DBYZ15A

1 Like

No, it is not necessary. You shouldn’t assume anything that is not specified in the problem statement.

1 Like

but in the solutions ppl checked the frequency of the data not the position…and…without given sorted data hw can u do that??

We will explain the solutions in editorials. Please wait for sometime.

no, it is not necessary that the array is already sorted as it is not mentioned in the question. Also if you want to calculate the frequency of the data you can use maps for that. here is a c++ code in which the same thing is done


`#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,num,ans;
cin>>n;
map<long long,long long> m;
for(int i=0;i<n;i++)
{
cin>>num;
m[num]++;
}

ans=n*(n-1)/2;

map<long long,long long>::iterator it=m.begin();
while(it!=m.end())
{
	ans-=(*it).second*((*it).second-1)/2;
	it++;
}
cout<<ans;
return 0;

} `


@sharru05:

solution copied from below link

http://www.codechef.com/viewsolution/6600986

2 Likes