In this HackerEarth Similar Chocolates problem solution, There are N chocolates denoted by array A where A[i] is the length of the i-th chocolate. Alice can melt each chocolate and then convert it into chocolate whose length is any divisor of the number A[i]. So, chocolate of length A[i] can be converted into X different types of chocolate where X is the count of divisors of the number A[i]. So you need to count the total unordered pair of chocolates such that their X value is the same.


HackerEarth Similar Chocolates problem solution


HackerEarth Similar chocolate problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[100001];
int divi[1000001];
LL f[1000001];
int main()
{
ios_base::sync_with_stdio(0);
int n;
for(int i = 1; i <= 1000000; i++){
for(int j = i; j <= 1000000; j += i){
divi[j]++;
}
}
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
f[divi[a[i]]]++;
}
LL ans = 0;
for(int i = 1; i <= 1000000; i++){
ans = ans + (f[i] * (f[i] - 1)) / 2;
}
cout << ans << endl;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

map<int, int> hash_map1;
map<int, int> hash_map2;

int divisors(int n) {
if(hash_map1.find(n) != hash_map1.end())
return hash_map1[n];
int cnt = 0;
for(int i = 1; i <= sqrt(n); i ++) {
if(n % i == 0) {
cnt ++;
if(n / i != i)
cnt ++;
}
}
hash_map1[n] = cnt;
return hash_map1[n];
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int inp;
for(int i = 0; i < n; i ++) {
cin >> inp;
hash_map2[divisors(inp)] ++;
}
long long ans = 0;
for(auto i : hash_map2) {
long long x = i.second;
ans += (x * (x - 1)) / 2;
}
cout << ans;
return 0;
}