If an NxM multiplication table is put in order, what is number in the middle?

Question

If I have a multiplication table sized, for example, 3x5:

1  2  3  4  5
2  4  6  8 10
3  6  9 12 15

And I put all these numbers in order:

1 2 2 3 3 4 4 5 6 6 8 9 10 12 15

What is the number in the middle? In this case, it's 5.

N and M are always odd, so there can be only one answer.

Is there a fast solution for this? I'm looking for something among the lines of O(N log NM)

This is homework of sorts, but I'm really lost with this one. I've come up with some ideas, but they all had some shortcomings:

public class Table {

    public static void main(String[] ar) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();

        int[] s = new int[w * h + 1];
        for (int i = 1; i <= w; i++)
            for (int j = 1; j <= h; j++)
                s[i * j] = s[i * j] + 1;

        int sum = 0;
        for (int i = 0; i < s.length; i++) {
            sum += s[i];
            if (sum >= s.length / 2) {
                System.out.println(i);
                break;
            }
        }
    }

}

This solves most of the tests fast enough (<4s), but for big N and M, the memory limits are exceeded (I don't know the exact limitations).

The idea is to keep track of the occurrences of each number, and then iterate through all the numbers in order, adding the number of occurrences each iteration. When the number of occurrences is higher or equal to w * h / 2, it is the number in the middle and we print it.

public class Table {

    public static void main(String[] ar) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();

        int sum = 0;
        for (int i = 1; i <= w * h; i++) {
            for (int j = 1; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    int k = i / j;
                    if (k <= w && k != j) sum++;
                    if (k <= h && k != j) sum++;
                    if (k <= w && k <= h && k == j) sum++;
                }                
            }

            if (sum >= (w * h + 1) / 2) {
                System.out.println(i);
                break;
            }
        }
    }

}

Trying to overcome the memory limits, I tried counting the occurrences of each number up to the middle one as they come. I noticed that the number of occurrences in a multiplication table of each number is the number of factors they have.

Not fast enough.

---

Can anyone come up with any pointers? I know that in the suggested O(N log NM) solution binary search is used.

---

1 <= N <= 10^5
1 <= M <= 10^5

---

Solution!

Ok, so thanks to @PeterdeRivaz I was able to find and implement a solution for my problem. The idea is as he describes it, and here's the actual implementation:

    public class Kertotaulu {


        public static void main(String[] ar) {
            Scanner scanner = new Scanner(System.in);
            long h = scanner.nextLong();
            long w = scanner.nextLong();


            long min = 1;
            long max = w*h;
            long mid = 0;
            while (min <= max) {
                mid = (min + max) / 2;
                long sum = 0;
                for (int i = 1; i <= h; i++) sum += Math.min(mid / i, w);
                sum--;


                if (sum < (w * h) / 2) min = mid + 1;
                else if (sum > (w * h) / 2) max = mid - 1;
                else break;
            }


            long sum = 0;
            for (int i = 1; i <= h; i++) sum += Math.min((mid - 1) / i, w);
            sum--;


            if (sum == (w * h) / 2) System.out.println(mid - 1);
            else System.out.println(mid);
        }


    }

Answer 1

You can use binary search on the value by counting how many entries in the multiplication table will be less than the value.

This will require log(NM) iterations in the binary search so we need to be able to compute the count in O(N) for a total complexity of O(Nlog(NM)).

This can be done by considering each multiplication table in turn. For example, suppose our test value is 8 and we are considering the 3 times table.

The values less than eight will be 3*1 and 3*2. We can find how many there are by simply dividing the test value 8 by the table 3 and rounding down, i.e. floor(8/3) = 2 so the 3 times table will give us a count of 2.