title: If an NxM multiplication table is put in order, what is number in the middle?
body: <p>If I have a multiplication table sized, for example, 3x5:</p>
  
  <pre><code>1  2  3  4  5
  2  4  6  8 10
  3  6  9 12 15
  </code></pre>
  
  <p>And I put all these numbers in order:</p>
  
  <pre><code>1 2 2 3 3 4 4 5 6 6 8 9 10 12 15
  </code></pre>
  
  <p>What is the number in the middle? In this case, it's 5.</p>
  
  <p><code>N</code> and <code>M</code> are always odd, so there can be only one answer.</p>
  
  <p>Is there a fast solution for this? I'm looking for something among the lines of <code>O(N log NM)</code></p>
  
  <p>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:</p>
  
  <pre><code>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 &lt;= w; i++)
              for (int j = 1; j &lt;= h; j++)
                  s[i * j] = s[i * j] + 1;
  
          int sum = 0;
          for (int i = 0; i &lt; s.length; i++) {
              sum += s[i];
              if (sum &gt;= s.length / 2) {
                  System.out.println(i);
                  break;
              }
          }
      }
  
  }
  </code></pre>
  
  <p>This solves most of the tests fast enough (&lt;4s), but for big N and M, the memory limits are exceeded (I don't know the exact limitations).</p>
  
  <p>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 <code>w * h / 2</code>, it is the number in the middle and we print it.</p>
  
  <pre><code>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 &lt;= w * h; i++) {
              for (int j = 1; j &lt;= Math.sqrt(i); j++) {
                  if (i % j == 0) {
                      int k = i / j;
                      if (k &lt;= w &amp;&amp; k != j) sum++;
                      if (k &lt;= h &amp;&amp; k != j) sum++;
                      if (k &lt;= w &amp;&amp; k &lt;= h &amp;&amp; k == j) sum++;
                  }                
              }
  
              if (sum &gt;= (w * h + 1) / 2) {
                  System.out.println(i);
                  break;
              }
          }
      }
  
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>Not fast enough.</p>
  
  <hr>
  
  <p>Can anyone come up with any pointers? I know that in the suggested <code>O(N log NM)</code> solution binary search is used.</p>
  
  <hr>
  
  <pre><code>1 &lt;= N &lt;= 10^5
  1 &lt;= M &lt;= 10^5
  </code></pre>
  
  <hr>
  
  <h1>Solution!</h1>
  
  <p>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:</p>
  
  <blockquote class="spoiler">
    <p> <pre>
      public class Kertotaulu {
  <br>
          public static void main(String[] ar) {
              Scanner scanner = new Scanner(System.in);
              long h = scanner.nextLong();
              long w = scanner.nextLong();
  <br>
              long min = 1;
              long max = w*h;
              long mid = 0;
              while (min &lt;= max) {
                  mid = (min + max) / 2;
                  long sum = 0;
                  for (int i = 1; i &lt;= h; i++) sum += Math.min(mid / i, w);
                  sum--;
  <br>
                  if (sum &lt; (w * h) / 2) min = mid + 1;
                  else if (sum > (w * h) / 2) max = mid - 1;
                  else break;
              }
  <br>
              long sum = 0;
              for (int i = 1; i &lt;= h; i++) sum += Math.min((mid - 1) / i, w);
              sum--;
  <br>
              if (sum == (w * h) / 2) System.out.println(mid - 1);
              else System.out.println(mid);
          }
  <br>
      }</pre></p>
  </blockquote>