Harmonic Lemma : H(n) - UVA 11526

• Case 1: $x\le \sqrt{n}$

  • Hence, if we divide $n$ with $1\le i\le x$, number of values of $\lfloor \frac{n}{i} \rfloor$ will be at most $x$ (because, if all values were different, even then there will be $x$ values). Which is equal to $\sqrt{n}$.

• Case 2: $x>\sqrt{n}$

  • Hence the values of $\lfloor \frac{n}{i} \rfloor$ (where $\sqrt{n} < i \le n$) will be in range $[\frac{n}{n},\frac{n}{\sqrt{n}}] = [1,\sqrt{n}]$.

  • $\therefore$ number of unique values of $\lfloor \frac{n}{i} \rfloor$ will be at most $\sqrt{n}$.

$\therefore$ Number of different values of $\lfloor \frac{n}{i} \rfloor$ is maximum $2\sqrt{n}$.

• Binary search
• Doing some division ….