Codechef |Coding Problem|Beautiful Pairs Problem

Problem Statement:

You are given a sequence A1,A2,…,AN. An ordered pair of indices (i,j) in this sequence is called a beautiful pair if i≠j and Ai−AjAi<Ai−AjAj. (Here, division represents real division, e.g. 52 is equal to 2.50.)

Help Chef find the number of beautiful pairs present in the given sequence.

Note: Since the input is large, prefer using fast input methods.

Input Format

• The first line of the input contains a single integer T

denoting the number of test cases. The description of T

• test cases follows.
• The first line of each test case contains a single integer N
• The second line contains N

space-separated integers A1,A2,…,AN

Output Format

For each test case, print a single line containing one integer — the number of beautiful pairs present in the given sequence.

Constraints

• 1≤T≤10
• 1≤N≤2⋅10^5
• 1≤Ai≤10^6 for each valid i

Subtasks

Subtask #1 (20 points): N≤10^3

Subtask #2 (80 points): original constraints

Sample Input 1

2
3
4 2 4
6
2 8 6 2 1 5

Sample Output 1

4
28

Explanation

Example case 1: The beautiful pairs of indices are (1,2),(2,1),(2,3),(3,2)

• For the pair (1,2) : (4−2)/4<(4−2)/2 since 0.5<1
• For the pair (2,1): (2−4)/2<(2−4)/4 since −1<−0.5
• For the pair (2,3): (2−4)/2<(2−4)/4 since −1<−0.5
• For the pair (3,2): (4−2)/4<(4−2)/2 since 0.5<1.

Code & Algorithm

/* author : @akash */
/* 
problem is:-
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mod 1000000007
#define ld long double
void solve()
{
  ll n;
  cin>>n;
  ll a[n];
  for(ll i=0;i<n;++i)
  {
   cin>>a[i];
  }
map<ll,ll>m;
  for(ll x:a)
  {
   m[x]++;
  }
  ll ans=n*(n-1);
  for(auto y:m)
  {
   if(y.second>1)
   {
    ans-=y.second*(y.second-1);
   }
  }
  cout<<ans;
}
int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 int t;
 cin>>t;
 while(t--)
 {
            solve();
            cout<<"\n";     
 }
 return 0;
}
// time complexity of this algorithm is : T(n)=O(n)

Thank You.

Akash Kumar

Software Engineer