# Hackerrank Solution: Sherlock and Pairs

Sherlock is given an array of \(N\) integers (\(A_0, A_1 \dots A_{N-1}\)) by Watson. Now Watson asks Sherlock how many different pairs of indices \(i\) and \(j\) exist such that \(i\) is not equal to \(j\) but \(A_i\) is equal to \(A_j\).

That is, Sherlock has to count the total number of pairs of indices \((i,j)\) where \(A_i=A_j\) and \(i\neq j\).

## Input Format

The first line contains \(T\), the number of test cases. \(T\) test cases follow.

Each test case consists of two lines; the first line contains an integer \(N\), the size of array, while the next line contains \(N\) space separated integers.

## Output Format

For each test case, print the required answer on a different line.

## Constraints

- \(1\leq T \leq 10\)
- \(1\leq N\leq 10^5\)
- \(1\leq A[i]\leq 10^6\)

## Solution

The easiest solution for this problem is an \(O(n^2)\) algorithm, that loops over the array twice and checks if the condition \(A_i=A_j\) and \(i\neq j\) holds for each pair \((i, j)\):

function solve(a) { let c = 0; for (let i = 0; i < a.length; i++) { for (let j = 0; j < a.length; j++) { if (i !== j && a[i] == a[j]) { c++; } } } return c; }

While this algorithm works for the first test cases, it fails later since the constraints state that the number of elements in the array can contain up to \(10^5\) elements.

But if we count each element in the array, we know that for each unique value \(k\) in the array and its count \(c_k\), exactly \(c_k^2 - c_k\) elements are possible, as it is a full permutation reduced by the number of occurences for \(i=j\). So, an \(O(n)\) solution can be found by storing all elements of the array in a hashmap and then sum over all unique numbers:

\[\sum_{k\in A} c_k(c_k - 1)\]

An implementation can then be stated like this:

function solve(a) { let s = 0, c = {}; for (let i = 0; i < a.length; i++) { c[a[i]] = (c[a[i]] || 0) + 1; } for (let k in c) { s+= c[k] * c[k] - c[k]; } return s; }

This solution has a space complexity of \(O(n)\). When we sort the array in-place first in \(O(n\log n)\), we can then solve the problem in \(O(n)\) with \(O(1)\) additional space requirements:

function solve(a) { a.sort((x, y) => x - y); let s = 0, c = 1, p = a[0]; for (let i = 1; i < a.length; i++) { if (a[i] == p) { c++; } else { s+= c * c - c; c = 1; } p = a[i]; } return s + c * c - c; }