Task — 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.

Examples

Example 1
Input: @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) = 1

Example 2
Input: @nums = (7, 7, 7, 7, 7, 7, 7)
Output: 49

Analysis

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.

Try it 

Script

#!/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);
}

Output

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