Task — Multiplication table

You are given 3 positive integers, $i, $j and $k. Write a script to print the $kth element in the sorted multiplication table of $i and $j.

Examples

Example 1
Input: $i = 2; $j = 3; $k = 4
Output: 3
Since the multiplication of 2 x 3 is as below:
    1 2 3
    2 4 6
The sorted multiplication table:
    1 2 2 3 4 6
Now the 4th element in the table is "3".

Example 2
Input: $i = 3; $j = 3; $k = 6
Output: 4
Since the multiplication of 3 x 3 is as below:
    1 2 3
    2 4 6
    3 6 9
The sorted multiplication table:
    1 2 2 3 3 4 6 6 9
Now the 6th element in the table is "4".

Analysis

There seem to be 2 options here:

1. Do it as per the examples, ie create the table, sort it and then look for the $kth element.
2. Device an ingenious way to calculate the value of the $kth element without calculating the table.

I completely failed with method 2, and my solution therefore uses method 1.

It is true that the calculation time for method 1 grows fast as $i and $j increase, so if anyone has a real need for this I suggest they look at other submitted responses for someone who has managed a solution using method 2.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2021-11-22
# PWC 140 task 2

use v5.20;
use warnings;
use strict;

my (@tests, $test, $i, $j, $k, @results, $i0, $j0);

# i, j, k sets to be tested
@tests = ([2, 3, 4], [3, 3, 6], [20, 30, 599], [1000, 999, 314159], [5, 6, 30]);

# loop over tests
for $test (@tests) {
    
    # we want the $nth product in $results[$n] so dummy out $results[0]
    @results = (0);
    ($i, $j, $k) = @$test;
    say qq[\nInput:  \$i = $i, \$j = $j, \$k = $k];
    if ($k > $i * $j or $k <= 0) {
        say qq[\$k must be in the range 1 .. ] . ($i * $j);
        next;
    }
    
    # make table
    for $i0 (1 .. $i) {
        for $j0 (1 .. $j) {
            push (@results, $i0 * $j0);
        }
    }
    
    # sort results and print desired one
    @results = sort {$a <=> $b} @results;
    
    say qq[Output: $results[$k]\n];
}

Output

Input:  $i = 2, $j = 3, $k = 4
Output: 3

Input:  $i = 3, $j = 3, $k = 6
Output: 4

Input:  $i = 20, $j = 30, $k = 599
Output: 580

Input:  $i = 1000, $j = 999, $k = 314159
Output: 93532