In this HackerEarth Shil and Birthday present problem solution Shil got an array of N integers as a present on his birthday. But he didn't liked it. Shil wants to make this array beautiful. Shil considers an array A1,A2,A3 . . . AN beautiful if A1 > AN. Inorder to make it beautiful Shil can swap any two numbers in the array. Also Shil can perform this operation any number of times on any adjacent pairs of integers in the array A.Find the number of ways in which Shil can make this array beautiful.Two ways are considered same if resulting array after making all the swaps have same A1 and AN.


HackerEarth Shil and Birthday present problem solution


HackerEarth Shil and Birthday present problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define mp make_pair
#define mod 1000000007
#define f first
#define s second
#define pb emplace_back
#define fr freopen("input-10.txt","r",stdin)
#define fo freopen("output-10.txt","w",stdout)
ll freq[1000011];
int main(){

ll n;
scanf("%d",&n);
ll x;
long long int t=0;
for(int i=1;i<=n;i++){
scanf("%d",&x);
freq[x]++;
if(freq[x]==1){
t++;
}
}
long long int ans=t*(t-1);
ans/=2;
cout<<ans;
}

Second solution

#include <bits/stdc++.h>
using namespace std ;
#define LL long long int

int N ;
vector<int> A ;

int main(){
cin >> N ;
assert(N <= 1000000 && N >= 1) ;
A.resize(N) ;
for(int i=0;i<N;i++){
cin >> A[i] ;
assert(A[i] <= 1000000 && A[i] >= 1) ;
}
sort(A.begin(),A.end()) ;
int i = 0 , distinct = 0 ;
LL ans ;
while(i < N){
distinct ++ ;
int x = A[i] ;
while(i < N && x == A[i]){
i ++ ;
}
}
ans = (1LL * distinct * (distinct-1) / 2) ;
cout << ans << endl ;
return 0 ;
}