Pairs on the floor

Weekly challenge 243 — 13 November 2023

Week 243 - 13 Nov 2023

Task 2

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.

Example 1Input: @nums = (2, 5, 9) Output: 10 floor(2 / 5) = 0 floor(2 / 9) = 0 floor(5 / 9) = 0 floor(2 / 2) = 1 floor(5 / 5) = 1 floor(9 / 9) = 1 floor(5 / 2) = 2 floor(9 / 2) = 4 floor(9 / 5) = 1Example 2Input: @nums = (7, 7, 7, 7, 7, 7, 7) Output: 49

This is similar to task 1 in that we need a nested pair of loops, iterating over `$i`

and
`$j`

. However,
there is an interesting difference, which is that task 1 depended of the __ordering__ of the supplied
array, but task 2 does not.

The first impact this makes is that instead of looping like this:`for $i (0 .. $last)`

and
then working with `$nums[$i]`

, we can use `for $m (@nums)`

and work
simply with `$m`

- and similaly with
`$j`

and `$n`

.

Since the order of the array is not significant we can make some savings by sorting it, because
then, in our loops, as soon as `$m`

gets to be less than `$n`

, we can abandon that `$m`

value. That's because any value of `$m`

less than `$n`

will result in the ratio `$m / $n`

being less than 1, thus having a floor
of zero. Also, by far the likeliest floor value (after 0) is 1, which will occur if
`$m`

is less than twice `$n`

.
By separating those cases out we can avoid a division, which is (marginally) slower.

These measures are of course insignificant if the array is short, and maybe even counterproductive because they require a sort. However, for a long array containing 10 000 random numbers in the range 0 .. 200, using the optimised version of the algorithm described above took my computer 23 seconds (and the floor sum was 242390694).

Without the optimisation it took 33 seconds (and the floor sum was the same!), so it provides a useful but hardly spectacular improvement.

#!/usr/bin/perl use v5.16; # The Weekly Challenge - 2023-11-13 use utf8; # Week 243 task 2 - Floor sum use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge floor_sum(2, 5, 9); floor_sum(7, 7, 7); # more interesting one my @nums; $nums[$_] = int(rand(100)) + 1 for 0 .. 10; floor_sum(@nums); sub floor_sum { my (@nums, $m, $n, $sum, $floor, $explain); # initialise and sort input $sum = $floor = 0; $explain = ''; @nums = sort {$a <=> $b} @_; # loop over m and n for $m (@nums) { for $n (@nums) { # skip the rest of the (sorted) $n's because $floor will be 0 last if $m < $n; # floor will be 1 if $m less than twice $n if ($m < $n * 2) { $floor = 1; # otherwsie do the division } else { $floor = int($m / $n); } $sum += $floor; $explain .= qq[floor($m / $n) = $floor~]; } } # reformat and display $explain =~ s/(.*?)~(.*?)~/sprintf(qq[ %-21s | %-21s\n], $1, $2)/egm; $explain =~ s|\nf|\n f|; say qq[\nInput: \@nums = (] . join(', ', @_) . ')'; say qq[Output: $sum\n] . substr($explain, 0, -1); }

Input: @nums = (2, 5, 9) Output: 10 floor(2 / 2) = 1 | floor(5 / 2) = 2 floor(5 / 5) = 1 | floor(9 / 2) = 4 floor(9 / 5) = 1 | floor(9 / 9) = 1 Input: @nums = (7, 7, 7) Output: 9 floor(7 / 7) = 1 | floor(7 / 7) = 1 floor(7 / 7) = 1 | floor(7 / 7) = 1 floor(7 / 7) = 1 | floor(7 / 7) = 1 floor(7 / 7) = 1 | floor(7 / 7) = 1 floor(7 / 7) = 1 Input: @nums = (76, 82, 49, 48, 15, 83, 33, 94, 83, 15, 7) Output: 192 floor(7 / 7) = 1 | floor(15 / 7) = 2 floor(15 / 15) = 1 | floor(15 / 15) = 1 floor(15 / 7) = 2 | floor(15 / 15) = 1 floor(15 / 15) = 1 | floor(33 / 7) = 4 floor(33 / 15) = 2 | floor(33 / 15) = 2 floor(33 / 33) = 1 | floor(48 / 7) = 6 floor(48 / 15) = 3 | floor(48 / 15) = 3 floor(48 / 33) = 1 | floor(48 / 48) = 1 floor(49 / 7) = 7 | floor(49 / 15) = 3 floor(49 / 15) = 3 | floor(49 / 33) = 1 floor(49 / 48) = 1 | floor(49 / 49) = 1 floor(76 / 7) = 10 | floor(76 / 15) = 5 floor(76 / 15) = 5 | floor(76 / 33) = 2 floor(76 / 48) = 1 | floor(76 / 49) = 1 floor(76 / 76) = 1 | floor(82 / 7) = 11 floor(82 / 15) = 5 | floor(82 / 15) = 5 floor(82 / 33) = 2 | floor(82 / 48) = 1 floor(82 / 49) = 1 | floor(82 / 76) = 1 floor(82 / 82) = 1 | floor(83 / 7) = 11 floor(83 / 15) = 5 | floor(83 / 15) = 5 floor(83 / 33) = 2 | floor(83 / 48) = 1 floor(83 / 49) = 1 | floor(83 / 76) = 1 floor(83 / 82) = 1 | floor(83 / 83) = 1 floor(83 / 83) = 1 | floor(83 / 7) = 11 floor(83 / 15) = 5 | floor(83 / 15) = 5 floor(83 / 33) = 2 | floor(83 / 48) = 1 floor(83 / 49) = 1 | floor(83 / 76) = 1 floor(83 / 82) = 1 | floor(83 / 83) = 1 floor(83 / 83) = 1 | floor(94 / 7) = 13 floor(94 / 15) = 6 | floor(94 / 15) = 6 floor(94 / 33) = 2 | floor(94 / 48) = 1 floor(94 / 49) = 1 | floor(94 / 76) = 1 floor(94 / 82) = 1 | floor(94 / 83) = 1 floor(94 / 83) = 1 | floor(94 / 94) = 1

Peter Campbell Smith is hereby placed in the public domain