If the NxM multiplication table is ordered, what is the number in the middle?

Question

If I have a multiplication table of size, 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 is 5.

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

Is there a quick fix for this? I am looking for something among the lines O(N log NM)

This is homework, but I really lost it. I came up with some ideas, but they all had some flaws:

 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 allows you to solve most of the tests quickly enough (<4s), but for large N and M the memory limits are exceeded (I do not know the exact limits).

The idea is to track the occurrences of each number, and then iterate over all the numbers in order, adding the number of occurrences to each iteration. When the number of occurrences is greater than or equal to w * h / 2 , this 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 memory limitations, I tried to count the numbers of each number to the average when they arrive. I noticed that the number of entries in the multiplication table of each number is the number of factors that they have.

Not fast enough.

---

Can anyone come up with any pointers? I know that the proposed O(N log NM) solution uses binary search.

---

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

---

Decision

Ok, so thanks to @PeterdeRivaz I was able to find and implement a solution for my problem. The idea is how he describes it, and here is 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 by value, counting how many entries in the multiplication table will be less than the value.

This will require iterations in the log (NM) in binary search, so that we can calculate the score in O (N) for the full complexity of O (Nlog (NM)).

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

Values ​​less than eight will be 3 * 1 and 3 * 2. We can find how much there is by simply dividing the test value of 8 by table 3 and rounding down, i.e. Sex (8/3) = 2, so the table 3 times will give us a score of 2.