CSES Solutions - Multiplication Table

Find the middle element when the numbers in an n × n multiplication table are sorted in increasing order. It is assumed that n is odd.

For example, the 3 × 3 multiplication table is as follows:

1 2 3
2 4 6
3 6 9

The numbers in increasing order are [1,2,2,3,3,4,6,6,9], so the answer is 3

Example:

Input: n = 3
Output: 3
Explanation: The 3x3 multiplication table is as follows:

1 2 3
2 4 6
3 6 9

The sorted elements are: [1, 2, 2, 3, 3, 4, 6, 6, 9]. The middle element is 3.

Input: n = 5
Output: 8
Explanation: The 5x5 multiplication table is as follows:

1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25

The sorted elements are: [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 8, 8, 9, 10, 10, 12, 12, 15, 15, 16, 20, 20, 25]. The middle element is 8.

Multiplication Table using Binary Search

The main observation here is to realize that we can use binary search to efficiently determine the middle element in the n x n multiplication table. We don't need to explicitly construct and sort the table, but rather use the properties of the multiplication table to count elements up to a certain value.

1. Binary Search Range: The minimum value in the multiplication table is 1 and the maximum value is n * n.
2. Counting Elements: For a given middle value mid, count how many numbers in the multiplication table are less than or equal to mid. This can be done row by row. For row i, the elements are i, 2*i, 3*i, ..., n*i. The number of elements in this row that are ≤ mid is min(n, ⌊mid / i⌋).
3. Adjusting Search Range: Use binary search to find the smallest value mid for which the count of elements ≤ mid is at least (n^2 + 1) / 2 (the middle position in the sorted list).

Step-by-step approach:

• Initialize low = 1 and high = n * n.
• While low < high:
  • Calculate mid = (low + high) / 2.
  • Count the number of elements in the multiplication table that are ≤ mid.
  • If the count is greater than or equal to (n^2 + 1) / 2, set high = mid.
  • Otherwise, set low = mid + 1.
• Return high as the middle element.

Below is the implementation of the above algorithm:

// C++ code
#include <bits/stdc++.h>
using namespace std;

long long multiplicationtable(long long n)
{
    // Initialize the search range for the binary search
    long long l = 1, h = n * n, mid, count;

    // Perform binary search
    while (l < h) {

        // Calculate the middle of the current range
        mid = (l + h) / 2;
        count = 0;

        // Count the number of elements in the
        // multiplication table less than or equal to mid
        // row by row
        for (long long i = 1; i <= n; i++)
            count += min(n, mid / i);

        // If count is greater than or equal to half of
        // total number of elements in the multiplication
        // table
        if (count >= (n * n + 1) / 2)
            // decrease the upper bound
            h = mid;
        else
            // increase the lower bound
            l = mid + 1;
    }

    // Return the upper bound as the answer
    return h;
}

// Driver code
int main()
{
    long long n = 3;
    cout << multiplicationtable(n) << endl;

    return 0;
}

// Java code
import java.util.*;

public class GFG {

    public static long multiplicationTable(long n)
    {
        // Initialize the search range for the binary search
        long l = 1, h = n * n, mid, count;

        // Perform binary search
        while (l < h) {

            // Calculate the middle of the current range
            mid = (l + h) / 2;
            count = 0;

            // Count the number of elements in each row of
            // the multiplication table that is less than or
            // equal to mid
            for (long i = 1; i <= n; i++)
                count += Math.min(n, mid / i);

            // If count is greater than or equal to half of
            // total number of elements in the
            // multiplication table
            if (count >= (n * n + 1) / 2)

                // Decrease the upper bound
                h = mid;
            else
                // Increase the lower bound
                l = mid + 1;
        }

        // Return the upper bound as the answer
        return h;
    }

    public static void main(String[] args)
    {
        long n = 3;
        System.out.println(multiplicationTable(n));

        n = 5;
        System.out.println(multiplicationTable(n));
    }
}

3
8

Time Complexity: O(n*log(n*n))
Auxiliary Space: O(1)