# General Approach to Solve Counting Pairs Problems

I have seen many problems which include counting pairs in an array.

For Example —

``````You are given an Array with some positive numbers (sorted/unsorted).
You need to find pairs such as (arr[i],arr[j]) , i<j<n with some
property given .
such as arr[i]*2 == arr[j] * 2 , arr[i] ^ arr[j] < arr[j] ^ arr[i] ,
i*arr[i] > j*arr[j] (== or <= or >= any condition ).
``````

I generally solve it using a sorting or hashmap approach for solving these problems. But in some cases, I’m getting TLE.

Anyone has any other ways to solve these problems?. thankx. What? These are properties of the pairs,
to brute force this see this code

``````for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(pow(arr[i] , arr[j]) < pow(arr[j],arr[i])
count++;
}
}``````

Assuming `*` stands for multiplication, this can be easily solved using the following ALGORITHM.

• `arr[i] * 2 == arr[j] * 2`, cancelling 2 on both sides, `arr[i] == arr[j]`.
• Now, it reduces to finding the number of pairs `(i, j); i != j` such that `a[i] = a[j]`.
• Calculate the frequencies of Array elements using HashMap or Dictionary.
• Initialise answer. `int ans = 0`
• For each key in the HashMap or Dictionary, calculate the number of combinations possible and add them to answer.

Pseudo Code:

``````int ans = 0;
count[i] = Number of times i occurs in given array.
for(int key: count) {
ans = ans + (count[key] * (count[key] - 1)) / 2;
}
return ans;
``````

Oh, I am really sorry, I thought `^` represents bitwise XOR.

This is a variant of the Counting Inversions Problem

`A[i]^A[j] < A[j] ^ A[i]` pairs. where `a^b` is `pow(a,b)` (^ is power operation).