Multiplication Table

Explicación

Se nos pide hallar la mediana de los números de una tabla de multiplicar de $n \times n$, donde $n$ es impar. Si $f(x)$ representa cuántos números de la tabla de multiplicar son menores o iguales que $x$, entonces la mediana tendrá al menos $\frac{n^2 + 1}{2}$ números menores o iguales que ella. Así, queremos hallar el menor $x$ tal que $f(x) \geq \frac{n^2 + 1}{2}$.

Para hallar $f(x)$, podemos recorrer cada fila de la tabla. Como los números de una fila son el número de columna multiplicado por el número de fila, podemos dividir $x$ por el número de fila para hallar cuántas columnas tienen un número menor o igual que $x$. Tomar el mínimo entre la cantidad de columnas y $n$ nos dirá cuántos números de esa fila son menores o iguales que $x$, y sumar sobre todas las filas nos dará $f(x)$, que guardamos en la variable $\texttt{leq}$.

Usando $\texttt{leq}$, podemos hacer búsqueda binaria hasta hallar la mediana. Si $\texttt{leq} \geq \frac{n^2 + 1}{2}$, asignamos $\texttt{high}$ a $\texttt{mid}$ porque $\texttt{mid}$ funciona y es una cota superior de la respuesta. En caso contrario, asignamos $\texttt{low}$ a $\texttt{mid} + 1$ porque $\texttt{mid}$ no funciona, así que los números menores que $\texttt{mid}$ tampoco funcionarán.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

#include <iostream>
using namespace std;
 
int main() {
	long long n;
	cin >> n;
	long long low = 1, high = n * n, mid, leq;
 
	// búsqueda binaria para obtener la mediana
	while (low < high) {
		mid = (low + high) / 2;
		leq = 0;
		for (int i = 1; i <= n; i++) { leq += min(n, mid / i); }
		if (leq >= (n * n + 1) / 2) {
			high = mid;
		} else {
			low = mid + 1;
		}
	}
	cout << high << endl;
	return 0;
}

import java.io.*;
import java.util.StringTokenizer;
 
public class MultiplicationTable {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		long n = io.nextInt();
		long low = 1, high = n * n, mid, leq;
 
		// búsqueda binaria para hallar la mediana
		while (low < high) {
			mid = (low + high) / 2;
			leq = 0;
			for (int i = 1; i <= n; i++) { leq += Math.min(n, mid / i); }
			if (leq >= (n * n + 1) / 2) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}
 
		io.println(high);
		io.close();
	}
}

n = int(input())
 
low = 1
high = n**2
 
# búsqueda binaria para hallar la mediana
while low < high:
	mid = (low + high) // 2
	leq = 0
 
	for i in range(0, n):
		leq += min(n, mid // (i + 1))
 
	if leq >= (n**2 + 1) / 2:
		high = mid
	else:
		low = mid + 1
 
print(high)