Finding Pairs

Given an array A of N numbers, find the number of distinct pairs (i, j) such that j >=i and A[i] = A[j].

The first line of the input contains a number of test cases T. Each test case have two lines, first line is the number N, followed by a line consisting of N integers which are the elements of array A.

For each test case print the number of distinct pairs.

Example:

Input:  n = 4, a = [1,2,3,4]
Output: 4

Approach

C++

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

long long findingPairs(long long n, long long a[])
{
    map<long long, long long> mp;
    for (long long i = 0; i < n; i++)
    {
        mp[a[i]]++;
    }
    long long ans = n;
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        long long x = it->second;
        if (x >= 2)
            ans += x * (x - 1) / 2;
    }
    return ans;
}
int main()
{

    long long n = 4;

    long long a[n] = {1, 2, 3, 4};

    cout << findingPairs(n, a) << "\n";

    return 0;
}