General Approach to Solve Counting Pairs Problems

general
1

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. :+1:

2

What? :no_mouth:

3

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++;
 }
}
4

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

5

@suman_18733097 Thanks for answering.
Can you give some insights on how to count these pairs -

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

I have stuck on this for so long.