RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved combinatorics and integer division. (Note that this ends today.)

Task 1: 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]

I could have done a two-loop check, but it seemed more fun to use combinations; I wrote combination generators for the languages that don't have them back in 211 task 2 and 233 task 2. (But Dijkstra's algorithm, which I used when writing my own generators, returns the elements in reverse order, which meant some of the code ended up being written differently.)

Scala does technically have a combination generator, but it eliminates duplicates when an element is repeated, so rather than build a set of indices for it and then combine that I ported over my Kotlin code.

Perl:

sub reversepairs($a) {
  return scalar grep {$_->[0] > 2 * $_->[1]} combinations($a, 2);
}

Task 2: Floor Sum

You are given an array of positive integers (>=1).

Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.

This is very straightforward in languages that have strong typing, so that the default behaviour when dividing two integers is to return an integer. Or which have an integer division operator.

PostScript:

/floorsum {
    2 dict begin
    /a exch def
    0
    a {
        /iv exch def
        a { iv idiv } map { add } reduce add
    } forall
    end
} bind def

which is perhaps more readily understood in JavaScript:

function floorsum(a) {
    let n = 0;
    for (let iv of a) {
        for (let jv of a) {
            n += Math.floor(iv / jv);
        }
    }
    return n;
}

Full code on github.