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

ANSWER

#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);
}

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.