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.

Powered By
CHP Adblock Detector Plugin | Codehelppro