Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Reverse Pairs

Hard
0/120
Average time to solve is 50m
profile
Contributed by
107 upvotes
Asked in companies
IBMD.E.Shaw

Problem statement

You are given an array/list say ‘ARR’ of size ‘N’. We call pair (i, j) a Reverse Pair when i < j and 'ARR[i]' > 2 * 'ARR[j]'.

Your task is to find the number of Reverse Pairs present in given 'ARR'.

For example :

For the array [50, 21, 9], if we follow 1-based indexing, the Reverse Pairs are (1, 2), (1, 3) and (2, 3). Thus, the total count i.e. the answer becomes 3.

Note :

A single index of the pair (i, j) can be used multiple times.
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
1 <= T <= 5    
2 <= N <= 3000
1 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the i-th elements in the array/list. 

Time Limit: 1 sec
Sample Input 1 :
1
6
1 2 3 2 3 1
Sample Output 1 :
2
Explanation Of Sample Input 1 :
Test case 1: 
Given that we follow 1-based indexing, for the array {1, 2, 3, 2, 1}, the pairs satisfying the conditions of Reverse Pairs are 
For i = 3, arr[i] = 3 and for j = 6, arr[j] = 1.
For i = 5, arr[i] = 3 and for j = 6, arr[j] = 1.
Hence there are two possible pairs.
Sample Input 2 :
2
6
6 4 8 2 1 3
5
2 4 3 5 1 
Sample Output 2 :
6
3
Explanation Of Sample Input 2 :
Test case 1: 
Given that we follow 1-based indexing,The possible pairs satisfying the conditions of Reverse Pairs are (1, 4), (1, 5), (2, 5), (3, 4), (3, 5), (3, 6). Thus, the answer is 6.

Test case 2: 
Given that we follow 1-based indexing, The possible pair of indices satisfying the above condition are (2, 5), (3, 5), (4, 5). Thus, the answer is 3.
Full screen
Console