Register | Login

Solutions of Equal pairs

Select solution language All Tiếng Việt English Other

Write solution here.

---

MayFreecs    Created at    5 likes

# explanation ## how to count number of pairs using frequency In order to count how many pairs there are depending on the frequency of a number we use this formula: $pairs = frequency * (frequency-1)/2$ Also let's not forget to use long long instead of int since we are dealing with $10^5$ values therefore the max value is around $~(10^5)^2$, which is bigger than an int can support Now that we know this, let's implement it # Solution `#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ int n, j; cin >> n; // i decided not to store all values in a vector, you can do that int max_value=0; //maximum value since we don't have an array to store everything vector <int> freq(100001, 0); //since the maximum value of a[i] is 10^5 for(int i=0; i<n; i++){ cin >> j; freq[j]++; if(max_value<j)max_value = j; } int sum=0; for(int j=0; j<=max_value; j++){ int num_pairs = freq[j]*(freq[j]-1)/2; sum+=num_pairs; } cout << sum << endl; }`