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

Problem of the day

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

```
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
```

```
1
6
1 2 3 2 3 1
```

```
2
```

```
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.
```

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

```
6
3
```

```
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.
```