Task — Reverse pairs

You are given an array of integers. Write a script to return the number of reverse pairs in the given array. A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].

Examples

Example 1
Input: @nums = (1, 3, 2, 3, 1)
Output: 2

(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2
Input: @nums = (2, 4, 3, 5, 1)
Output: 3

(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Analysis

The easy way to do this is simply two nested loops, $i from 0 .. $last - 1 and $j from $i + 1 to $last, and then test each of these pairs. That completes in milliseconds even for 1000 random numbers.

However, it's even faster if we create an array @nums2 with each member twice the corresponding number in @nums. The test then simplifies to $nums[$i] > $nums2[$j]. So that's what I did.

Try it 

Script

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-11-13
use utf8;     # Week 243 task 1 - Reverse pairs
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

binmode(STDOUT, ':utf8');

reverse_pairs(1, 3, 2, 3, 1);
reverse_pairs(2, 4, 3, 5, 1);
reverse_pairs(1, 1, 1, 1, 1);

my (@nums, $i);
for $i (0 .. 10) {
    @nums[$i] = int(rand(200)) + 1;
}
reverse_pairs(@nums);

sub reverse_pairs {
    
    my (@nums, @nums2, $last, $i, $j, $k, $pairs, $explain);
    
    # initialise
    @nums = @_;
    $last = @nums - 1;
    $pairs = 0;
    $explain = '';
    @nums2 = map {$_ * 2} @nums;
    
    # loop over i and j
    for $i (0 .. $last - 1) {
        for $j ($i + 1 .. $last) {
            
            # test for condition
            if ($nums[$i] > $nums2[$j]) {
                $pairs ++;
                $explain .= qq[   \$nums[$i] = $nums[$i], \$nums[$j] = $nums[$j] ∵ $nums[$i] > $nums2[$j]] . qq[\n];
            }
        }
    }
    
    say qq[\nInput:  \@nums = (] . join(', ', @nums) . ')';
    say qq[Output: $pairs] . ($explain ? (qq[\n] . substr($explain, 0, -1)) : '');
}

Output

Input:  @nums = (1, 3, 2, 3, 1)
Output: 2
   $nums[1] = 3, $nums[4] = 1 ∵ 3 > 2
   $nums[3] = 3, $nums[4] = 1 ∵ 3 > 2

Input:  @nums = (2, 4, 3, 5, 1)
Output: 3
   $nums[1] = 4, $nums[4] = 1 ∵ 4 > 2
   $nums[2] = 3, $nums[4] = 1 ∵ 3 > 2
   $nums[3] = 5, $nums[4] = 1 ∵ 5 > 2

Input:  @nums = (1, 1, 1, 1, 1)
Output: 0

Input:  @nums = (69, 131, 142, 65, 146, 66, 104, 85, 81, 70, 43)
Output: 10
   $nums[1] = 131, $nums[3] = 65 ∵ 131 > 130
   $nums[1] = 131, $nums[10] = 43 ∵ 131 > 86
   $nums[2] = 142, $nums[3] = 65 ∵ 142 > 130
   $nums[2] = 142, $nums[5] = 66 ∵ 142 > 132
   $nums[2] = 142, $nums[9] = 70 ∵ 142 > 140
   $nums[2] = 142, $nums[10] = 43 ∵ 142 > 86
   $nums[4] = 146, $nums[5] = 66 ∵ 146 > 132
   $nums[4] = 146, $nums[9] = 70 ∵ 146 > 140
   $nums[4] = 146, $nums[10] = 43 ∵ 146 > 86
   $nums[6] = 104, $nums[10] = 43 ∵ 104 > 86