You are given 3 positive integers,
$i,$jand$k.Write a script to print the
$kth element in the sorted multiplication table of$iand$j.
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.
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.
It's tempting to just calculate all the products \(m \cdot n, 1 \leq m \leq i, 1 \leq n \leq j\), sort them, and take the \(k^{\text{th}}\) number. This works well for tiny numbers, but it will quickly use a large amount of memory. Below is a graph of the amount of memory used in a Perl program when creating a list of all the products \(m \cdot n, 1 \leq m, n \leq i\) (we are assuming \(i = j\)). As we can see, it grows quadratically, and we will be using more than 1 Gb of memory when \(i = j = 5750\), while we use more than 2 Gb of memory when \(i = j = 8000\).
Implementations in other languages may use less memory (because they require less memory to store on integer), but they will show that same quadratic behaviour.
Such a list would contain \(\mathcal{O} (i \cdot j)\) elements. If we generate the numbers in the list column by column, or row by row, we can sort them in \(\mathcal{O} (i \cdot j \cdot \log (\text{min} (i, j)))\), which dominates the running time.
For \(i = \Theta(j)\), we get a running time of \(\mathcal{O} (i^2 \log i)\), with a memory usage of \(\mathcal{O} (i^2)\).
Below, we have a table with values \(i \cdot j\). We can easily see that this table has the property that the values in each column (and each row), strictly increase:
| i | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … | ||
| j | 1 | 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
… |
| 2 | 2 |
4 |
6 |
8 |
10 |
12 |
14 |
16 |
18 |
20 |
… | |
| 3 | 3 |
6 |
9 |
12 |
15 |
18 |
21 |
24 |
27 |
30 |
… | |
| 4 | 4 |
8 |
12 |
16 |
20 |
24 |
28 |
32 |
36 |
40 |
… | |
| 5 | 5 |
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
… | |
| 6 | 6 |
12 |
18 |
24 |
30 |
36 |
42 |
48 |
54 |
60 |
… | |
| 7 | 7 |
14 |
21 |
28 |
35 |
42 |
49 |
56 |
63 |
70 |
… | |
| 8 | 8 |
16 |
24 |
32 |
40 |
48 |
56 |
64 |
72 |
80 |
… | |
| 9 | 9 |
18 |
27 |
36 |
45 |
54 |
63 |
72 |
81 |
90 |
… | |
| 10 | 10 |
20 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
100 |
… | |
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ||
We can make use of this property to not calculate and store all the values.
Instead, we will be using a heap \(\mathcal{H}\). In this heap, we store the columns of the table above — or rather, the highest number in each column we haven't processed.
We intialize the heap with the top values of each column (thus, the numbers \(1 \ldots i\)). We then repeat the following \(k - 1\) times:
Now, the \(k^\text{th}\) element will be the top of \(\mathcal{H}\).
We will never have more than \(i\) elements in \(\mathcal{H}\). Building a heap takes time linear to the size of the heap, so we can build the heap in \(\mathcal{O} (i)\) time.
Getting the minimum element from a heap takes constant time. Rebalancing a heap (after remove or replacing the top element) takes \(\mathcal{O} (\log i)\).
So, the running time of this algorithm is \(\mathcal{O} (k \cdot \log i)\), while using \(\mathcal{O} (i)\) memory.
Since \(k\) can be as large as \(i \cdot j\), the asymptotic running time is not an improvement of the naive algorithm, but the memory usage is a huge improvement.
The \(k^\text{th}\) element of the multiplication table will not exceed \(k\). In fact, other than the extreem cases, \(k = 1\) and \(k = i \cdot j\), the answer will be less than \(k\).
For each number \(n\), we can easily determine how often \(n\) appears in the multiplication table.
For each divisor \(d\) of \(n\), such that \(d \leq i\) and \(\frac{n}{d} \leq j\), \(n\) appears exactly once in the multiplication table of \(i\) and \(j\).
So, we can just count numbers \(n\), starting from \(1\), find all its divisors, and use this to calculate how often \(n\) appears in the multiplication table. It's then easy to keep track of which number appears on place \(k\).
To find all divisors \(d\) of a given number \(n\), we just look at all numbers \(c, 1 \leq c \leq \sqrt{n}\). If \(n \text{ mod } c = 0\), then both \(c\) and \(\frac{n}{c}\) are divisors of \(n\).
So, we can find all divisors of a number \(n\) in \(\mathcal{O}(\sqrt{n})\) time.
The number of divisors of \(n\) is \(\mathcal{o} (n^\epsilon)\) for all \(\epsilon > 0\).
This means the running time of this algorithm is \(\mathcal{O} (k \sqrt{k})\). The memory usage is either constant, or, if we produce a list of all divisors, \(\mathcal{o} (k^\epsilon)\) for all \(\epsilon > 0\).
Each solution will read lines from standard input. Each line consists
of three numbers, i, j, and k. For each line of input, it writes a
line of output.
We will not perform any input validation. We assume each of i, j, and k
are positive integers, and that k <= i * j.
This one is pretty straightforward:
while (<>) {
my ($i, $j, $k) = split;
say +(sort {$a <=> $b} map {my $l = $_; map {$_ * $l} 1 .. $j} 1 .. $i)
[$k - 1];
}
A nested map to calculate all the products, then we sort them and take the right value from the sorted list.
Find the full program on GitHub.
What we will be storing in the heap will be pairs of numbers: $i, which indicates the column of the multiplication table, and $j, which will indicate the row in the multiplication table. The product of those numbers will be the value in the table.
We will implement our heap as an array, where a node on index $p
has its children on indices 2 * $p + 1 and 2 * $p + 2. (This is
a very standard way of implementing a fixed size heap).
Creating a heap is easy — if the values in the array are sorted, it's automatically a heap:
sub make_heap ($i) {[map {[$_, 1]} 1 .. $i]}
Next, we need a couple of helper functions: prod takes a pair and
returns its product, and left and right which take an index, and
return the index of the left and right child:
sub prod ($pair) {$$pair [0] * $$pair [1]}
sub left ($index) {2 * $index + 1}
sub right ($index) {2 * $index + 2}
Then we need a method to rebalance a heap. It's called with the index
of the one element which is 'out of order' — 0 by default:
sub rebalance ($heap, $index = 0) {
my $index1 = left $index; # Left child
my $index2 = right $index; # Right child
return if $index1 > $#$heap; # No children, so we're done.
my $p = prod $$heap [$index];
#
# Find the smallest of the children
#
my $p1 = prod $$heap [$index1];
if ($index2 <= $#$heap) {
my $p2 = prod $$heap [$index2];
#
# Right child is smaller than left child, so right child wins
#
if ($p2 < $p1) {
$p1 = $p2;
$index1 = $index2;
}
}
#
# Now, $p1 is the smallest child, and on index $index1.
# If the smallest child is smaller than the current element,
# swap, and recurse. Else, we're done.
#
if ($p1 < $p) {
@$heap [$index, $index1] = @$heap [$index1, $index];
rebalance ($heap, $index1);
}
}
The function is recursive. It terminates if either the out of order node doesn't have any children, or none of its children are less than the node itself. Otherwise, we swap the node with the lesser of its children, and recurse.
Finally, the main program:
while (<>) {
my ($i, $j, $k) = split;
($j, $i) = ($i, $j) if $j < $i;
my $heap = make_heap ($i);
while ($k -- > 1) {
$$heap [0] [1] = $$heap [0] [1] >= $j ? $i * $j + 1
: $$heap [0] [1] + 1;
rebalance ($heap);
}
say prod $$heap [0];
}
Note that we don't actually delete an element from the heap. If we have reached the bottom of the column, we replace it with such a high value it exceeds the maximum value in the multiplication table, so it will never bubble to the top again.
Find the full program on GitHub.
We now want to find all the divisors of a given number.
Math::Prime::Util has a function fordivsors which does
exactly that. It takes a code reference and a number n as arguments,
and calls the code reference for each divisor of n.
So, we can just count up from 1, count the divisors d for each number,
such that d <= i and n / d <= j, and stop if we have seen k divisors:
while (<>) {
my ($n, $i, $j, $k) = (0, split);
fordivisors {$_ <= $i && $n / $_ <= $j && !-- $k && say $n} ++ $n
while $k >= 1;
}
Find the full program on GitHub.
For other languages, we only implement the algorithm which counts divisors. We won't be using libraries which returns all the divisors, so to get the divisors of a number \(n\), we just try each number \(1 \leq d \leq \frac{n}{d}\): if \(n \text{ mode } d = 0\), then both \(d\) and \(\frac{n}{d}\) are divisors of \(n\).
Which leads the following program (here, we have already read i, j,
and k):
n := int64 (0)
for ;k > 0; {
n ++
s := int64 (math . Sqrt (float64 (n)))
for d := int64 (1); d <= s && k > 0; d ++ {
if (n % d == 0) {
if (d <= i && n / d <= j) {k --}
if (d <= j && n / d <= i) {k --}
if (n == d * d) {k ++}
}
}
}
fmt . Println (n)
Note the special case when n is a proper square. In that case, we do not
want to count its square root as a divisor twice.
Find the full program on GitHub.
We also have implementations (all very similar to the Go implementation) in AWK, Bash, bc, C, Java, Lua, Node.js, Pascal, Python, R, Ruby, Scheme, and Tcl.