# Finding Pairs

QUESTION

Given an array A of N numbers, find the number of distinct pairs (i, j) such that j >=i and A[i] = A[j].\n\nFirst line of the input contains number of test cases T. Each test case has two lines, first line is the number N, followed by a line consisting of N integers which are the elements of array A.\n\nFor each test case print the number of distinct pairs.\n\nConstraints\n1 <= T <= 10\n1 <= N <= 10^6 \n-10^6 <= A[i] <= 10^6 for 0 <= i < N.

“TESTCASE_1”: “3\n4\n1 2 3 4\n3\n1 2 1\n5\n1 1 1 1 1\n###—###SEPERATOR—###—\n4\n4\n15”, “TESTCASE_2”: “2\n5\n-5 6 1 1 6\n9\n-4 2 -4 2 6 -8 4 7 7\n###—###SEPERATOR—###—\n7\n12”, “TESTCASE_3”: “3\n28\n871127 838258 838258 897424 -891471 217520 180702 -225967 543180 543180 838258 871127 180702 5449 5449 -225967 386153 389718 498464 -891471 180702 217520 389718 217520 -891471 897424 5449 5449\n15\n338393 900661 -182404 721485 701646 -288171 -747588 746206 -287554 -691235 -247687 -691235 -355541 -691235 -708040\n45\n414510 414510 -898031 46812 -898031 46812 -898031 414510 712935 46812 -898031 712935 414510 46812 712935 414510 -898031 414510 46812 46812 -898031 712935 414510 712935 46812 -898031 712935 -898031 712935 46812 712935 46812 712935 -898031 414510 46812 46812 712935 712935 414510 -898031 712935 -898031 414510 414510\n###—###SEPERATOR—###—\n51\n18\n276”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(false);
int tc; cin>>tc;
while (tc--)
{
int n; cin>>n;
vector<int> vec(n,0);
for (int i = 0; i < n; i++)
{
cin>>vec[i];
}
sort(vec.begin(), vec.end());
long long int cnt = 0;
int i = 0, j = 0;
while (i < vec.size() && j < vec.size())
{
if (vec[j] == vec[i])
cnt += j - i;
else
i = j;
j++;
}

cout<<cnt + vec.size()<<"\n";
}
return (0);
}``````